0 1
1 2
2 2
3 7
4 5
5 11
6 21
7 24
8 31
9 49
10 57
11 85
12 114
13 144
14 179
15 251
16 306
17 390
18 511
19 619
20 772
21 1008
22 1203
23 1498
24 1862
25 2255
26 2757
27 3407
28 4067
29 4927
30 6005
31 7180
32 8581
33 10395
34 12266
35 14652
36 17542
37 20673
38 24452
39 29057
40 34058
41 40172
42 47332
43 55341
44 64719
45 75999
46 88401
47 103051
48 120225
49 139348
50 161670
51 187943
52 216899
53 250838
54 289982
55 333892
56 384547
57 443104
58 508329
59 583549
60 669879
61 766615
62 876972
63 1003773
64 1144857
65 1306474
66 1490501
67 1696043
68 1929634
69 2195389
70 2491655
71 2828286
72 3208740
73 3633847
74 4113639
75 4656583
76 5261130
77 5943090
78 6711018
79 7566568
80 8528391
81 9610589
82 10812969
83 12163686
84 13676936
85 15360382
86 17244571
87 19353540
88 21694437
89 24311316
90 27233039
91 30475762
92 34090144
93 38121698
94 42586549
95 47560453
96 53093947
97 59220092
98 66028235
99 73593492
100 81957596
101 91243198
102 101538974
103 112916230
104 125519616
105 139483409
106 154890494
107 171940593
108 190796319
109 211586107
110 234556789
111 259934240
112 287876875
113 318720266
114 352738414
115 390174396
116 431432781
117 476893336
118 526860634
119 581874121
120 642411508
121 708901081
122 782005664
123 862375402
124 950545498
125 1047405771
126 1153756959
127 1270342938
128 1398264153
129 1538589218
130 1692270154
131 1860742557
132 2045339800
133 2247356853
134 2468568507
135 2710755675
136 2975543622
137 3265243898
138 3582085489
139 3928234486
140 4306583503
141 4720037560
142 5171333634
143 5664212225
144 6202302472
145 6789238080
146 7429659004
147 8128275986
148 8889677357
149 9719812353
150 10624606902
151 11610025554
152 12683477571
153 13852598024
154 15124890133
155 16509848227
156 18017000927
157 19656046988
158 21438811754
159 23377472941
160 25484264644
161 27774177996
162 30262430734
163 32964716015
164 35899671016
165 39086700122
166 42545452221
167 46299487972
168 50373023134
169 54791067782
170 59582964792
171 64779310086
172 70411394998
173 76516157907
174 83131681940
175 90297662156
176 98059899637
177 106466348105
178 115566550645
179 125417898645
180 136080080867
181 147615449840
182 160095127787
183 173593956327
184 188189511443
185 203970725121
186 221030362034
187 239465691380
188 259386735409
189 280909298907
190 304154251346
191 329258460451
192 356365257702
193 385625564666
194 417208327702
195 451292020439
196 488063426240
197 527732161197
198 570518647084
199 616655135553
200 666400094999
201 720026737581
202 777821923313
203 840105378847
204 907213698026
205 979502573710
206 1057365080217
207 1141217275354
208 1231497413674
209 1328690233897
210 1433307493893
211 1545890373874
212 1667033805474
213 1797368503122
214 1937559532675
215 2088338931870
216 2250480266218
217 2424802509647
218 2612202304851
219 2813630220801
220 3030090769012
221 3262683758022
222 3512572794478
223 3780991318175
224 4069283547111
225 4378876047364
226 4711277513713
227 5068132968688
228 5451185002185
229 5862280931487
230 6303427899330
231 6776756080927
232 7284520370289
233 7829171261444
234 8413305159498
235 9039676669950
236 9711268827124
237 10431248317603
238 11202970255900
239 12030068031192
240 12916394311180
241 13866036655091
242 14883409910061
243 15973202199212
244 17140381397061
245 18390314007577
246 19728691008295
247 21161551341971
248 22695403266438
249 24337156251211
250 26094135880980
251 27974235137118
252 29985825790576
253 32137793168916
254 34439691113934
255 36901663605709
256 39534465937658
257 42349661856070
258 45359518837711
259 48577054041393
260 52016240126880
261 55691909208813
262 59619788498823
263 63816757040896
264 68300717965102
265 73090668884203
266 78206965961988
267 83671213723447
268 89506322064578
269 95736834005760
270 102388781997319
271 109489783147822
272 117069385430746
273 125158944075074
274 133791702266894
275 143003222115892
276 152831215484091
277 163315681743521
278 174499361526734
279 186427593646463
280 199148443505626
281 212713255969542
282 227176469149944
283 242595812049062
284 259032889343521
285 276553035985095
286 295225499117460
287 315124159207887
288 336327332432193
289 358918040938943
290 382984786119676
291 408621394985372
292 435927290111894
293 465008430704180
294 495977101182696
295 528952303018514
296 564060756345816
297 601436762859163
298 641222600759518
299 683569738718320
300 728638646674580
301 776599334723198
302 827632669119490
303 881930276504390
304 939695098151483
305 1001142986775147
306 1066502544990200
307 1136015886011060
308 1209940363678290
309 1288548536736353
310 1372128977194857
311 1460988340751988
312 1555451290800610
313 1655861566996291
314 1762584238682565
315 1876005813853396
316 1996535369119908
317 2124607264023778
318 2260681216863411
319 2405243773716692
320 2558811290590029
321 2721930236795677
322 2895178798970573
323 3079170443056352
324 3274554210864556
325 3482016786677114
326 3702286398890351
327 3936133460872450
328 4184372833157049
329 4447868469395539
330 4727534116758069
331 5024336155279934
332 5339298747571224
333 5673504992561575
334 6028100060206369
335 6404297324232775
336 6803379619205942
337 7226703179481088
338 7675704440949578
339 8151901914193835
340 8656900588619208
341 9192399964990377
342 9760196189924920
343 10362187501888423
344 11000383172144884
345 11676906509007744
346 12394000932949370
347 13154040568213728
348 13959533662919503
349 14813130039776351
350 15717632955772848
351 16676003653207977
352 17691369781223512
353 18767039373141597
354 19906506060331556
355 21113459354566584
356 22391800283555533
357 23745648216775988
358 25179352494246395
359 26697510814051755
360 28304977121751989
361 30006875638938321
362 31808621576916745
363 33715931180356949
364 35734837646891047
365 37871715477395537
366 40133292025899052
367 42526666697598462
368 45059338399178466
369 47739220006180894
370 50574660258397666
371 53574475871606954
372 56747968319478266
373 60104950037615519
374 63655780706843931
375 67411388049507934
376 71383297674177986
377 75583675572240171
378 80025352189953000
379 84721857989993184
380 89687471629734954
381 94937249347716952
382 100487065684644122
383 106353669738208974
384 112554719197845924
385 119108828739729069
386 126035633781849234
387 133355831845802436
388 141091237963942756
389 149264859009050612
390 157900941685042010
391 167025037982931752
392 176664089735766513
393 186846486406128362
394 197602140111511078
395 208962584147153280
396 220961039849956720
397 233632505160614255
398 247013866743143949
399 261143980014489099
400 276063770839904170
401 291816365797458726
402 308447184993946114
403 326004061631042117
404 344537390420375259
405 364100238203295623
406 384748481108740930
407 406540977030279400
408 429539693719639605
409 453809869634784009
410 479420210768067914
411 506443042364384805
412 534954493811429983
413 565034726939282337
414 596768111622314532
415 630243442232219154
416 665554198099643698
417 702798751030632880
418 742080613994669843
419 783508742891115898
420 827197776754833394
421 873268327951601822
422 921847327053765828
423 973068305504586761
424 1027071729074071335
425 1084005397168311007
426 1144024769454091642
427 1207293354631768516
428 1273983166795653125
429 1344275108628680902
430 1418359418331049253
431 1496436197062593696
432 1578715851916539614
433 1665419615781137661
434 1756780150374531272
435 1853042064743682784
436 1954462512380122536
437 2061311888023785334
438 2173874426333189529
439 2292448895290396563
440 2417349393336556038
441 2548906047886346498
442 2687465812226052780
443 2833393385399628606
444 2987072018156146384
445 3148904437196147091
446 3319313897123098149
447 3498745119402200804
448 3687665353915377207
449 3886565591802147768
450 4095961648350358288
451 4316395391777163300
452 4548436131041160566
453 4792681874492621795
454 5049760740765465028
455 5320332557788330563
456 5605090312578976865
457 5904761783026152065
458 6220111367119387892
459 6551941764970887535
460 6901095852139120040
461 7268458784647207009
462 7654959935935538348
463 8061575060206316966
464 8489328700331535811
465 8939296431705757118
466 9412607343909969710
467 9910446810411156510
468 10434059069982971621
469 10984750089157555901
470 11563890730497079324
471 12172919737364309449
472 12813347017266421386
473 13486757282605480532
474 14194813481926328354
475 14939260583320085276
476 15721929737168022693
477 16544742239093415169
478 17409713866899356093
479 18318959660377829457
480 19274698474278847989
481 20279257969172312919
482 21335080076660696952
483 22444726249966973626
484 23610883182149150443
485 24836369077357837557
486 26124139677308160459
487 27477294836588844632
488 28899085690233352495
489 30392921594823222629
490 31962377658917374262
491 33611202960103012438
492 35343328507764258014
493 37162875892797158004
494 39074166676018972854
495 41081731549386949836
496 43190320235159598312
497 45404912243152874602
498 47730727371672794014
499 50173237067443765791
500 52738176712866749656
501 55431557691964351949
502 58259680386377867116
503 61229148242895532172
504 64346881593993359562
505 67620132559263543958
506 71056501105438008526
507 74663950912332897933
508 78450826409554326756
509 82425871150624437951
510 86598245974396588555
511 90977548520425977348
512 95573834199722776398
513 100397637021469708085
514 105459991892272928376
515 110772458593497182234
516 116347145601876901992
517 122196735614919355142
518 128334512903254646931
519 134774390600874479552
520 141530939856613104542
521 148619421084100737045
522 156055815156931428886
523 163856856748957774075
524 172040069967013293076
525 180623804058668140370
526 189627271463759680747
527 199070588501564843542
528 208974816158081433970
529 219362003571411152825
530 230255234405616795885
531 241678673493518261639
532 253657616442627056761
533 266218542550403605635
534 279389168046417152204
535 293198502741330799716
536 307676910305375315025
537 322856169107354316833
538 338769536797280070373
539 355451819043722409897
540 372939438937042283877
541 391270510682996258127
542 410484917872300602408
543 430624392719345068889
544 451732600028356138139
545 473855226392854942676
546 497040070524919069827
547 521337139004268369919
548 546798747794541208091
549 573479625292752852078
550 601437021365607648903
551 630730822964904205699
552 661423671531161867798
553 693581087241080645385
554 727271600521965299913
555 762566885889634409181
556 799541903351153171372
557 838275048100398639771
558 878848302898511271275
559 921347399093938539859
560 965861986821486702280
561 1012485808578985882356
562 1061316882383725590333
563 1112457695379901005697
564 1166015401340368941090
565 1222102029098688195717
566 1280834702556057335151
567 1342335865504156163951
568 1406733518573126026040
569 1474161469349039708329
570 1544759588032454222602
571 1618674076902671899888
572 1696057754405570642443
573 1777070345971743275508
574 1861878790175045350667
575 1950657561516986992206
576 2043589000923244781644
577 2140863663706435011658
578 2242680685998196922778
579 2349248160444501938325
580 2460783531337359142114
581 2577514010710013069266
582 2699677005048355448490
583 2827520564090920454320
584 2961303852949281633783
585 3101297636864104550694
586 3247784790551231163479
587 3401060834017471272831
588 3561434482812029769878
589 3729228226202543663664
590 3904778934832919844201
591 4088438485412417135013
592 4280574416546957077579
593 4481570617983683653997
594 4691828039291702224318
595 4911765433881568482554
596 5141820140253727306369
597 5382448886062503860562
598 5634128631599712336354
599 5897357455446524225618
600 6172655466134093535311
601 6460565758474118942970
602 6761655416941849123905
603 7076516549398842761831
604 7405767370688854040256
605 7750053339496441999334
606 8110048329723510770702
607 8486455858369524089571
608 8880010372855735964851
609 9291478578444240297394
610 9721660828790383264754
611 10171392583709642272458
612 10641545912547961854186
613 11133031068990019711584
614 11646798140937855060490
615 12183838753163376058877
616 12745187849793044817430
617 13331925561660390267084
618 13945179133581916565900
619 14586124941910917874058
620 15255990606937335082242
621 15956057174364870222830
622 16687661397765329661009
623 17452198128147827944167
624 18251122781899184093748
625 19085953922844129650604
626 19958275964029187171581
627 20869741959634534732218
628 21822076524534198631741
629 22817078888996811698691
630 23856626055556978521457
631 24942676100010675885046
632 26077271623568920333054
633 27262543322151536597799
634 28500713716953742633393
635 29794101055546998965652
636 31145123345609261515416
637 32556302570687583002847
638 34030269096709950376626
639 35569766230223493969834
640 37177654980386837314716
641 38856919035989248879865
642 40610669914183553294270
643 42442152338999257009628
644 44354749860444490824102
645 46351990669652932119855
646 48437553671220869993373
647 50615274826677668631039
648 52889153719583406731954
649 55263360410515695533454
650 57742242595491152926531
651 60330333016883205267931
652 63032357198930054146963
653 65853241524945163841958
654 68798121599778039587744
655 71872350977942092468534
656 75081510274132613639493
657 78431416598265635922905
658 81928133399906986650434
659 85577980743116730579439
660 89387545947664258191757
661 93363694691113035869537
662 97513582592704151112462
663 101844667213316615854251
664 106364720571444799700519
665 111081842201232914003064
666 116004472679832632474680
667 121141407735461228210808
668 126501812962150219817475
669 132095239066768525447247
670 137931637766250193950409
671 144021378366966245162883
672 150375264944201634412460
673 157004554252854273488553
674 163920974401638578645448
675 171136744207030669155184
676 178664593365819919442796
677 186517783485838550017152
678 194710129882440016093458
679 203256024295153058980799
680 212170458564856150065304
681 221469049177172697148130
682 231168062836067396231957
683 241284443116432115779030
684 251835838091919411888900
685 262840629120261442978439
686 274317960836043264731131
687 286287772245616466430102
688 298770829117619457730763
689 311788757729295632471340
690 325364079852952094369366
691 339520249197272010034244
692 354281689365856958184459
693 369673833215666339973707
694 385723163843742331234808
695 402457257276837356886847
696 419904826735149661443313
697 438095768723810428182528
698 457061211029617056178652
699 476833562492990543019186
700 497446564825289251308090
701 518935346563425135820734
702 541336479019685793501938
703 564688034526231127253072
704 589029647070537519874634
705 614402575178977613760292
706 640849767367641655911436
707 668415930274380823615516
708 697147599315959911375242
709 727093212224147635261958
710 758303185580750326553799
711 790829994195255926484171
712 824728253702994910186861
713 860054806524676624261450
714 896868811017085889630306
715 935231834233769513725734
716 975207948444486993459276
717 1016863831244462571619612
718 1060268869700841776674265
719 1105495268710471766699196
720 1152618163385584377978598
721 1201715735962738152833990
722 1252869337420264513931999
723 1306163613623082139143087
724 1361686636524988645276607
725 1419530040644248839127428
726 1479789164616215067196325
727 1542563198410224053258763
728 1607955336440736189590396
729 1676072936381048189993786
730 1747027684308809837413344
731 1820935766449846421812723
732 1897918047314042967726866
733 1978100254919439214640147
734 2061613173389947393375729
735 2148592842727864692660678
736 2239180766507645532790332
737 2333524127821136181775974
738 2431776013260803663707819
739 2534095645766956138867505
740 2640648626693794766291103
741 2751607186891536162236676
742 2867150447692106871193612
743 2987464692206708027936979
744 3112743646719443474052728
745 3243188773158767742764210
746 3379009573086409079691423
747 3520423903004260904486013
748 3667658302034556357419790
749 3820948332478167414548860
750 3980538933040757945661541
751 4146684785893376411387088
752 4319650698113483935207314
753 4499711997318055862775837
754 4687154942744792690642436
755 4882277152406525950661388
756 5085388046122662746912590
757 5296809305816737674146095
758 5516875353756786596505228
759 5745933848573048979087082
760 5984346200550369523600194
761 6232488106967387569295502
762 6490750107315339081681116
763 6759538160050958193967708
764 7039274241721884992786649
765 7330396968338874085040917
766 7633362240779737023592139
767 7948643915180380065096464
768 8276734498191907109334893
769 8618145869076336178410533
770 8973410029680454259943070
771 9343079882221326907213916
772 9727730037015204767820489
773 10127957651330287267546538
774 10544383299312332638831752
775 10977651875338491766557870
776 11428433532085390052921469
777 11897424653333793775654044
778 12385348864056770390407168
779 12892958079249573992291940
780 13421033591553018392075492
781 13970387200483164104645259
782 14541862384860029701463409
783 15136335518581495275012796
784 15754717132788203025756017
785 16397953226221886597947969
786 17067026623970303655724595
787 17762958387963705697623641
788 18486809281192625582205868
789 19239681285963707215155651
790 20022719179841110356856700
791 20837112171497674407895506
792 21684095596865502529200884
793 22564952679613288398115576
794 23481016358385366580584947
795 24433671181351696601224838
796 25424355272437756951475692
797 26454562371981204651658218
798 27525843952467520377988682
799 28639811414169204288289141
800 29798138363699166287622531
801 31002562976334082056827298
802 32254890447348848880036082
803 33556995535750876119833574
804 34910825201415149462846182
805 36318401341407135373794305
806 37781823629210204328534720
807 39303272458120829519531753
808 40885011995101914066279550
809 42529393349273265236888967
810 44238857856500745754606413
811 46015940487027665827216838
812 47863273380738497758798630
813 49783589511847608395422255
814 51779726490568920781224393
815 53854630506920691454576168
816 56011360418722505922799050
817 58253091992127043775638064
818 60583122300349355643952742
819 63004874283072061616815616
820 65521901475612704564694518
821 68137892914202494024585537
822 70856678220207890442829698
823 73682232873323315576580382
824 76618683680717466433739440
825 79670314445497060647741605
826 82841571845417565102404164
827 86137071529664177220699927
828 89561604437525908428932949
829 93120143351026700929040639
830 96817849690122282119476133
831 100660080554954024775700634
832 104652396028321829761669425
833 108800566748007254754710372
834 113110581754036118205322952
835 117588656625407678347594784
836 122241241916891993579212479
837 127075031901827962272458733
838 132096973636779234940596803
839 137314276359899582150740361
840 142734421229710974740747955
841 148365171421792755300641777
842 154214582596437632323652046
843 160291013745029988447058438
844 166603138434263078067751124
845 173159956462776507514133157
846 179970805938953827918579710
847 187045375800978503095411498
848 194393718795212454836066046
849 202026264922954811155059655
850 209953835378645400820825074
851 218187656997436076985192073
852 226739377223446117357423406
853 235621079624150340701930508
854 244845299970655249258367991
855 254425042896823375134164619
856 264373799165080342458991710
857 274705563560933311597810342
858 285434853430751124413264348
859 296576727893519276364331328
860 308146807750856773199422131
861 320161296111888174913686706
862 332636999766588378577475400
863 345591351334654922764979019
864 359042432208512090904061758
865 373008996327538536191517707
866 387510494813349916311967699
867 402567101487285492753942359
868 418199739310712855933154378
869 434430107781361929826533544
870 451280711309367297733649410
871 468774888617823359877628456
872 486936843204485294724584376
873 505791674891444396112237238
874 525365412511865518932791297
875 545685047774541799616602602
876 566778570336263294145966000
877 588675004136155383930259359
878 611404445036939197907426240
879 634998099807015416553069324
880 659488326502731029854758748
881 684908676300802827975034983
882 711293936818767808964705910
883 738680176988935088823184427
884 767104793540970158122415642
885 796606559135810627502668460
886 827225672222703819064084335
887 859003808680626887613646587
888 891984175291728649215057365
889 926211565125978350303999359
890 961732414904608071997731399
891 998594864395945307853068408
892 1036848817930500954469817027
893 1076546008110360173408815269
894 1117740061772623404205390138
895 1160486568302702161193902650
896 1204843150380263816752351600
897 1250869537224929271403658530
898 1298627640446844138722283607
899 1348181632594013074286197248
900 1399598028471136430866116639
901 1452945769345871248129852381
902 1508296310143903421825102098
903 1565723709716619492090765547
904 1625304724308617525818714098
905 1687118904337522306609578325
906 1751248694579344557265838605
907 1817779537899696532114553678
908 1886799982654937685012992170
909 1958401793867628919151691783
910 2032680068330347266812907607
911 2109733353775415391420118219
912 2189663772226623769835183484
913 2272577147702793718474182584
914 2358583138424936418069988431
915 2447795373656773205442104728
916 2540331595365132637020558800
917 2636313804868401050605609401
918 2735868414617218817076474751
919 2839126405313050235479134947
920 2946223488550154687835775960
921 3057300275141942121488951108
922 3172502449357580664026501217
923 3291980949274348335229890495
924 3415892153424500662014420428
925 3544398073985638808730142436
926 3677666556741244062718290189
927 3815871488010754598684536095
928 3959193008822706340953576944
929 4107817736581894551848592898
930 4261938994451823581172285741
931 4421757048753915094690877364
932 4587479354660282404943128524
933 4759320810426558032265019624
934 4937504020496014991103892470
935 5122259567781322499595501600
936 5313826295397313681198538462
937 5512451598209826786273003620
938 5718391724538459071680367903
939 5931912088317484214698093655
940 6153287592116093172030302962
941 6382802961391676542290922470
942 6620753090313422187002178330
943 6867443399598268503002690095
944 7123190206771321930380600636
945 7388321109225759627138892102
946 7663175380568002481999612165
947 7948104380703875573891314696
948 8243471980081232088773782294
949 8549654998624273757378904971
950 8867043659862032089560563554
951 9196042060712581001982677209
952 9537068657511250109914765104
953 9890556768838232207888652413
954 10256955095656700800006894334
955 10636728259409496647201414412
956 11030357358686646422844525576
957 11438340545031113622490643694
958 11861193618595065804616803817
959 12299450644323182547175082790
960 12753664589290999768607162099
961 13224407981982840046959076050
962 13712273594255042322927648813
963 14217875146681094774646065122
964 14741848038141020205473930294
965 15284850100478697220263301444
966 15847562378997733567101251441
967 16430689939745623030540347163
968 17034962704493928762767121716
969 17661136314268727173497887327
970 18309993022475238805321068853
971 18982342618618929723331149168
972 19679023383567684439646853826
973 20400903077504546358162822048
974 21148879961675433162853339650
975 21923883854978240738925522225
976 22726877226656815673788908470
977 23558856326318848169841214016
978 24420852352434251037437627152
979 25313932660705084021962313558
980 26239202013650051832427921230
981 27197803872683989582374693215
982 28190921734221344060141486251
983 29219780511285558082397981067
984 30285647962038987350891082334
985 31389836166916478860957650656
986 32533703055994909408123892407
987 33718653988163927837476334136
988 34946143383947834518621152478
989 36217676413779132910402180203
990 37534810743452365832261987899
991 38899158338794279414595831710
992 40312387331533257494448652378
993 41776223948279576278964019108
994 43292454504854225803069805105
995 44862927468152924361609195252
996 46489555587655532020201380189
997 48174318099043373300940821043
998 49919263002332106817159564675
999 51726509416852478335489109753
1000 53598250015785255272325874230