0 1
1 1
2 1
3 2
4 1
5 2
6 3
7 3
8 5
9 6
10 7
11 9
12 10
13 12
14 15
15 18
16 22
17 26
18 31
19 36
20 42
21 50
22 58
23 68
24 80
25 92
26 107
27 124
28 142
29 164
30 189
31 216
32 248
33 284
34 323
35 369
36 420
37 476
38 541
39 613
40 693
41 784
42 885
43 997
44 1123
45 1264
46 1419
47 1593
48 1787
49 2000
50 2239
51 2504
52 2795
53 3120
54 3479
55 3874
56 4313
57 4797
58 5329
59 5918
60 6567
61 7279
62 8065
63 8930
64 9877
65 10921
66 12067
67 13320
68 14699
69 16209
70 17860
71 19672
72 21653
73 23817
74 26186
75 28774
76 31597
77 34682
78 38048
79 41714
80 45715
81 50074
82 54816
83 59984
84 65607
85 71718
86 78368
87 85594
88 93439
89 101964
90 111218
91 121254
92 132146
93 143956
94 156750
95 170620
96 185642
97 201900
98 219506
99 238554
100 259151
101 281430
102 305510
103 331524
104 359633
105 389988
106 422750
107 458116
108 496273
109 537418
110 581794
111 629628
112 681165
113 736700
114 796510
115 860900
116 930223
117 1004821
118 1085068
119 1171390
120 1264209
121 1363979
122 1471216
123 1586436
124 1710191
125 1843107
126 1985811
127 2138974
128 2303353
129 2479709
130 2668859
131 2871714
132 3089197
133 3322299
134 3572115
135 3839766
136 4126447
137 4433477
138 4762211
139 5114090
140 5490703
141 5893679
142 6324757
143 6785844
144 7278899
145 7806020
146 8369487
147 8971658
148 9615053
149 10302398
150 11036529
151 11820462
152 12657459
153 13550920
154 14504453
155 15521959
156 16607501
157 17765394
158 19000293
159 20317049
160 21720819
161 23217146
162 24811817
163 26510983
164 28321237
165 30249478
166 32303027
167 34489721
168 36817771
169 39295880
170 41933357
171 44739955
172 47726011
173 50902566
174 54281193
175 57874159
176 61694538
177 65756050
178 70073229
179 74661543
180 79537242
181 84717518
182 90220659
183 96065881
184 102273502
185 108865124
186 115863437
187 123292434
188 131177596
189 139545692
190 148425025
191 157845614
192 167839012
193 178438564
194 189679605
195 201599290
196 214236856
197 227633858
198 241833997
199 256883398
200 272830890
201 289727812
202 307628339
203 326589786
204 346672406
205 367939772
206 390459085
207 414301000
208 439540040
209 466254928
210 494528444
211 524447852
212 556105296
213 589597662
214 625027044
215 662501204
216 702133424
217 744043048
218 788355982
219 835204564
220 884728182
221 937073804
222 992395901
223 1050857120
224 1112628874
225 1177891316
226 1246834059
227 1319656866
228 1396569654
229 1477793292
230 1563560395
231 1654115346
232 1749715216
233 1850630644
234 1957145909
235 2069559980
236 2188187472
237 2313358814
238 2445421415
239 2584740726
240 2731700520
241 2886704162
242 3050175833
243 3222560906
244 3404327354
245 3595967160
246 3797996771
247 4010958713
248 4235423168
249 4471988552
250 4721283357
251 4983967889
252 5260735040
253 5552312338
254 5859463907
255 6182991449
256 6523736508
257 6882582726
258 7260457021
259 7658332133
260 8077229197
261 8518219130
262 8982425539
263 9471027611
264 9985261777
265 10526425016
266 11095878081
267 11695047525
268 12325429415
269 12988592968
270 13686182989
271 14419924015
272 15191624467
273 16003179518
274 16856575749
275 17753895889
276 18697322133
277 19689141442
278 20731750893
279 21827661551
280 22979504491
281 24190036798
282 25462146139
283 26798857543
284 28203340181
285 29678912724
286 31229050945
287 32857395444
288 34567757843
289 36364129364
290 38250689609
291 40231813676
292 42312081901
293 44496289772
294 46789456141
295 49196834264
296 51723922967
297 54376476166
298 57160515315
299 60082342034
300 63148549097
301 66366034441
302 69742015501
303 73284041814
304 77000010833
305 80898184177
306 84987202035
307 89276101076
308 93774332809
309 98491780065
310 103438777269
311 108626131136
312 114065139581
313 119767614591
314 125745905601
315 132012921150
316 138582154627
317 145467710761
318 152684330303
319 160247419074
320 168173077947
321 176478130903
322 185180157889
323 194297528648
324 203849434661
325 213855926269
326 224337950801
327 235317388984
328 246817096789
329 258860948463
330 271473877958
331 284681926056
332 298512289003
333 312993365527
334 328154809960
335 344027587160
336 360644025785
337 378037878243
338 396244382616
339 415300323040
340 435244097325
341 456115786697
342 477957224274
343 500812071230
344 524725895379
345 549746248764
346 575922753358
347 603307189688
348 631953584591
349 661918307690
350 693260171290
351 726040529502
352 760323386929
353 796175511126
354 833666544578
355 872869127076
356 913859022219
357 956715243946
358 1001520194174
359 1048359805140
360 1097323682259
361 1148505258826
362 1202001956236
363 1257915345070
364 1316351319019
365 1377420275120
366 1441237295252
367 1507922341714
368 1577600459803
369 1650401982288
370 1726462749228
371 1805924335534
372 1888934281315
373 1975646338760
374 2066220727764
375 2160824395260
376 2259631292344
377 2362822661446
378 2470587328044
379 2583122011716
380 2700631648624
381 2823329719418
382 2951438598392
383 3085189915376
384 3224824924240
385 3370594894676
386 3522761518088
387 3681597321688
388 3847386107824
389 4020423409178
390 4201016953848
391 4389487157756
392 4586167635123
393 4791405720436
394 5005563020302
395 5229015985668
396 5462156497321
397 5705392484300
398 5959148564978
399 6223866703676
400 6500006903385
401 6788047923700
402 7088488017020
403 7401845704132
404 7728660578053
405 8069494129094
406 8424930612864
407 8795577950150
408 9182068651075
409 9585060786336
410 10005238994240
411 10443315515366
412 10900031279133
413 11376157030240
414 11872494486720
415 12389877555122
416 12929173590015
417 13491284689838
418 14077149055336
419 14687742397518
420 15324079387137
421 15987215172690
422 16678246954016
423 17398315602866
424 18148607358817
425 18930355587407
426 19744842591238
427 20593401504270
428 21477418255329
429 22398333591593
430 23357645193768
431 24356909868190
432 25397745807005
433 26481834949079
434 27610925426712
435 28786834089270
436 30011449137507
437 31286732853801
438 32614724418834
439 33997542850250
440 35437390048285
441 36936553938399
442 38497411748623
443 40122433405830
444 41814185041033
445 43575332643329
446 45408645845941
447 47317001834968
448 49303389421821
449 51370913262655
450 53522798215587
451 55762393878102
452 58093179288323
453 60518767780417
454 63042912038749
455 65669509334442
456 68402606934109
457 71246407728231
458 74205276062033
459 77283743758934
460 80486516386531
461 83818479747245
462 87284706584559
463 90890463556616
464 94641218459421
465 98542647690949
466 102600644009965
467 106821324572408
468 111211039236323
469 115776379192085
470 120524185900919
471 125461560332552
472 130595872562263
473 135934771709817
474 141486196211777
475 147258384490680
476 153259886003167
477 159499572659786
478 165986650682591
479 172730672883058
480 179741551353889
481 187029570643682
482 194605401398049
483 202480114460888
484 210665195508641
485 219172560201814
486 228014569847715
487 237204047651914
488 246754295542623
489 256679111563184
490 266992807914589
491 277710229632258
492 288846773894315
493 300418410046986
494 312441700332451
495 324933821318051
496 337912586116473
497 351396467384190
498 365404621097875
499 379956911203741
500 395073935128551
501 410777050153154
502 427088400749763
503 444030946872409
504 461628493203807
505 479905719465790
506 498888211783837
507 518602495112103
508 539076066831521
509 560337431513794
510 582416136860533
511 605342810936057
512 629149200689829
513 653868211780038
514 679533949824149
515 706181763075335
516 733848286538911
517 762571487663104
518 792390713605333
519 823346740092111
520 855481822015401
521 888839745769216
522 923465883349803
523 959407248370163
524 996712553996885
525 1035432272837670
526 1075618698938877
527 1117326011906573
528 1160610343183787
529 1205529844653800
530 1252144759588237
531 1300517495977663
532 1350712702426564
533 1402797346636120
534 1456840796519387
535 1512914904142827
536 1571094092523036
537 1631455445331674
538 1694078799714277
539 1759046842259221
540 1826445208178212
541 1896362583916850
542 1968890813240521
543 2044125006865013
544 2122163655865564
545 2203108748918710
546 2287065893455411
547 2374144440976267
548 2464457616592092
549 2558122652879644
550 2655260928320973
551 2755998110399694
552 2860464303457310
553 2968794201595812
554 3081127246712321
555 3197607791782802
556 3318385269700322
557 3443614367768360
558 3573455207980095
559 3708073533411384
560 3847640900843352
561 3992334879760940
562 4142339258080193
563 4297844254735690
564 4459046739293058
565 4626150458965460
566 4799366273182783
567 4978912395899918
568 5165014646049692
569 5357906706310020
570 5557830390394123
571 5765035919298534
572 5979782206702374
573 6202337153749884
574 6432977953684213
575 6671991406551130
576 6919674244230466
577 7176333466300196
578 7442286686978105
579 7717862493428838
580 8003400815980196
581 8299253310522856
582 8605783753415175
583 8923368449477698
584 9252396653385308
585 9593271004814872
586 9946407977977345
587 10312238345880522
588 10691207659718340
589 11083776744065512
590 11490422208264718
591 11911636974444106
592 12347930822899196
593 12799830955269656
594 13267882575996526
595 13752649492852864
596 14254714737025992
597 14774681203290600
598 15313172311127706
599 15870832687322048
600 16448328870634738
601 17046350039473810
602 17665608763156152
603 18306841777418816
604 18970810785177870
605 19658303283193774
606 20370133415368612
607 21107142853756608
608 21870201708016812
609 22660209464109138
610 23478095953404293
611 24324822353013536
612 25201382218223636
613 26108802548302528
614 27048144886568141
615 28020506455696564
616 29027021329638640
617 30068861643133440
618 31147238839892275
619 32263404960936972
620 33418653974184720
621 34614323146460064
622 35851794459543743
623 37132496071462388
624 38457903824318704
625 39829542800407592
626 41248988927944655
627 42717870637838392
628 44237870573396970
629 45810727354432288
630 47438237397335239
631 49122256793171400
632 50864703245410550
633 52667558069017402
634 54532868253127491
635 56462748589084854
636 58459383865736970
637 60525031134402456
638 62662022045464235
639 64872765258669916
640 67159748929761520
641 69525543275580264
642 71972803219933013
643 74504271123064996
644 77122779597098000
645 79831254409942680
646 82632717480772107
647 85530289969650416
648 88527195464065336
649 91626763265718056
650 94832431780419007
651 98147752014100909
652 101576391178593762
653 105122136410286192
654 108788898604973601
655 112580716372853067
656 116501760117090846
657 120556336239580112
658 124748891478189279
659 129084017379258483
660 133566454909306354
661 138201099210617904
662 142993004504834999
663 147947389148884587
664 153069640848321364
665 158365322032601680
666 163840175397030985
667 169500129616904877
668 175351305238788942
669 181400020754126678
670 187652798861175927
671 194116372920686663
672 200797693610998635
673 207703935789078806
674 214842505563424593
675 222221047585042617
676 229847452563588437
677 237729865015154576
678 245876691248492573
679 254296607597372743
680 262998568906178731
681 271991817276150864
682 281285891080656025
683 290890634257242819
684 300816205884583675
685 311073090053412528
686 321672106039938407
687 332624418790587421
688 343941549727973659
689 355635387887368528
690 367718201393336843
691 380202649287301539
692 393101793716168165
693 406429112492562806
694 420198512038384903
695 434424340722742645
696 449121402605788699
697 464304971601181436
698 479990806069255705
699 496195163853473931
700 512934817773993345
701 530227071591540194
702 548089776455310215
703 566541347849934709
704 585600783055911615
705 605287679138468304
706 625622251481203957
707 646625352880228491
708 668318493215118399
709 690723859714463280
710 713864337833151133
711 737763532759186089
712 762445791569363905
713 787936226052506768
714 814260736219657453
715 841446034522241410
716 869519670798588863
717 898510057969966110
718 928446498508949779
719 959359211702378536
720 991279361731931009
721 1024239086597146926
722 1058271527905131757
723 1093410861552055256
724 1129692329323418917
725 1167152271439511040
726 1205828160073401363
727 1245758633870796562
728 1286983533500539583
729 1329543938265545102
730 1373482203806037989
731 1418842000926447866
732 1465668355578406747
733 1514007690034476678
734 1563907865286757795
735 1615418224705705734
736 1668589638996782377
737 1723474552492132757
738 1780127030815743699
739 1838602809962966392
740 1898959346834898237
741 1961255871269476439
742 2025553439613705197
743 2091914989881094792
744 2160405398539859163
745 2231091538980132687
746 2304042341708176663
747 2379328856317136430
748 2457024315286771685
749 2537204199664361943
750 2619946306680703721
751 2705330819358139130
752 2793440378167414873
753 2884360154792012617
754 2978177928061796329
755 3074984162117763268
756 3174872086871668647
757 3277937780827694793
758 3384280256333361175
759 3494001547329016730
760 3607206799668859225
761 3724004364086549815
762 3844505891880813343
763 3968826433400227324
764 4097084539406644455
765 4229402365399199945
766 4365905778984894309
767 4506724470382118660
768 4651992066146186555
769 4801846246210229033
770 4956428864335326417
771 5115886072066657032
772 5280368446297010013
773 5450031120539672945
774 5625033920015849071
775 5805541500666610936
776 5991723492200227387
777 6183754645289104015
778 6381814983035726225
779 6586089956828018992
780 6796770606708211153
781 7014053726384764273
782 7238142033018167734
783 7469244341915359474
784 7707575746273361463
785 7953357802114189487
786 8206818718557366154
787 8468193553582581582
788 8737724415436759655
789 9015660669844404701
790 9302259153186723958
791 9597784391817005790
792 9902508827684728859
793 10216713050447923867
794 10540686036255602570
795 10874725393387463480
796 11219137614945591529
797 11574238338795502949
798 11940352614959703542
799 12317815180674943520
800 12706970743327349527
801 13108174271485891617
802 13521791294263206232
803 13948198209236181090
804 14387782599165494505
805 14840943557762444034
806 15308092024755211968
807 15789651130514055798
808 16286056550504665879
809 16797756869843225220
810 17325213958234634642
811 17868903355585782922
812 18429314668590561411
813 19006951978591874940
814 19602334261037042630
815 20215995816848365310
816 20848486716039868097
817 21500373253923151378
818 22172238420251269758
819 22864682381659537698
820 23578322977774915545
821 24313796231372278862
822 25071756872966662722
823 25852878880244210324
824 26657856032741939173
825 27487402482198089880
826 28342253339009415038
827 29223165275239951724
828 30130917144638394395
829 31066310620136817404
830 32030170849312543682
831 33023347128308529056
832 34046713594724386789
833 35101169940000148818
834 36187642141829526398
835 37307083217157384326
836 38460473996327124191
837 39648823918959522824
838 40873171852163798488
839 42134586931693769786
840 43434169426679089179
841 44773051628582136536
842 46152398765044460960
843 47573409939305129864
844 49037319095895445477
845 50545396013329091880
846 52098947324526713568
847 53699317565737643372
848 55347890254737497825
849 57046088999101895384
850 58795378635381994784
851 60597266400025072788
852 62453303132906627374
853 64365084514367778152
854 66334252336670923288
855 68362495810811731278
856 70451552909654822866
857 72603211748381493912
858 74819312003264934878
859 77101746369819838686
860 79452462061396229040
861 81873462349316594844
862 84366808145689180194
863 86934619630055312834
864 89579077921060241488
865 92302426794373208228
866 95106974448109787578
867 97995095317043633404
868 100969231936933698832
869 104031896860322775970
870 107185674625200017478
871 110433223777961904388
872 113777278952138590058
873 117220653004392268894
874 120766239209339136634
875 124417013514781863026
876 128176036858982353631
877 132046457551652854706
878 136031513720381917510
879 140134535824257995692
880 144358949236505326595
881 148708276897988577498
882 153186142043492667208
883 157796271002739909782
884 162542496078152117291
885 167428758501419169894
886 172459111470995459636
887 177637723272695063978
888 182968880485614610359
889 188456991275677190042
890 194106588779144390348
891 199922334578506191446
892 205909022273227716753
893 212071581147890125048
894 218415079940330555700
895 224944730712460480628
896 231665892826505078639
897 238584077029479205882
898 245704949648795558644
899 253034336901969265034
900 260578229323461832531
901 268342786311793413518
902 276334340800126803066
903 284559404053611433176
904 293024670596868153965
905 301737023275076300722
906 310703538452216038826
907 319931491350118496200
908 329428361532063635347
909 339201838534764488052
910 349259827652683399012
911 359610455878720640772
912 370262078005422171181
913 381223282890968385676
914 392502899894308302350
915 404110005483918341746
916 416053930024788623375
917 428344264748350780468
918 440990868910184954994
919 454003877140476756366
920 467393706992315187185
921 481171066693055832576
922 495346963104116808256
923 509932709894705019752
924 524939935935113973775
925 540380593915388402993
926 556266969195291637944
927 572611688891666545816
928 589427731209446499503
929 606728435022724978607
930 624527509712459325000
931 642839045267562332264
932 661677522656299849455
933 681057824475092437127
934 700995245882010753524
935 721505505822432152686
936 742604758554519767029
937 764309605482391496057
938 786637107305038439948
939 809604796489261127866
940 833230690075113625323
941 857533302822553150139
942 882531660708217809396
943 908245314781493544966
944 934694355389255564565
945 961899426778911899013
946 989881742089633213964
947 1018663098741895127034
948 1048265894235720324267
949 1078713142368283654337
950 1110028489881804790469
951 1142236233552934200166
952 1175361337735134911353
953 1209429452365844721471
954 1244466931450506305107
955 1280500852035871833884
956 1317559033685293226631
957 1355670058469035261449
958 1394863291482992011095
959 1435168901909515649670
960 1476617884634417834743
961 1519242082434572989175
962 1563074208750907319209
963 1608147871061935473094
964 1654497594873403724297
965 1702158848339980952841
966 1751168067535345717755
967 1801562682387444647196
968 1853381143296109736831
969 1906662948450660326583
970 1961448671865574631965
971 2017779992152760330660
972 2075699722049425396097
973 2135251838721044030299
974 2196481514859391907319
975 2259435150596132634516
976 2324160406252968145493
977 2390706235949882468773
978 2459122922093554693079
979 2529462110768587705654
980 2601776848054756178859
981 2676121617294065247579
982 2752552377332025011305
983 2831126601758146065256
984 2911903319171293967445
985 2994943154496200346277
986 3080308371378074858395
987 3168062915682942996118
988 3258272460132044051371
989 3351004450099320006643
990 3446328150601758562007
991 3544314694513116017002
992 3645037132032295906033
993 3748570481438447197607
994 3854991781165665562427
995 3964380143230989108886
996 4076816808050227513647
997 4192385200677044602567
998 4311170988501584336837
999 4433262140445841772940
1000 4558748987693927647859