0 1
1 1
2 1
3 1
4 1
5 2
6 3
7 3
8 3
9 3
10 5
11 7
12 9
13 9
14 9
15 11
16 15
17 19
18 21
19 21
20 25
21 31
22 39
23 45
24 49
25 53
26 63
27 75
28 87
29 97
30 107
31 121
32 143
33 165
34 187
35 207
36 233
37 265
38 303
39 341
40 381
41 425
42 479
43 541
44 611
45 681
46 761
47 849
48 951
49 1063
50 1185
51 1315
52 1465
53 1631
54 1817
55 2019
56 2241
57 2483
58 2755
59 3051
60 3379
61 3733
62 4125
63 4557
64 5037
65 5559
66 6131
67 6753
68 7441
69 8195
70 9023
71 9915
72 10895
73 11963
74 13141
75 14429
76 15831
77 17349
78 19011
79 20823
80 22811
81 24965
82 27303
83 29837
84 32611
85 35631
86 38923
87 42483
88 46345
89 50539
90 55113
91 60067
92 65445
93 71251
94 77551
95 84387
96 91811
97 99835
98 108523
99 117907
100 128081
101 139089
102 150999
103 163845
104 177735
105 192729
106 208951
107 226463
108 245365
109 265741
110 287743
111 311461
112 337063
113 364637
114 394353
115 426351
116 460849
117 497983
118 537983
119 581009
120 627319
121 677131
122 730737
123 788349
124 850305
125 916855
126 988395
127 1065243
128 1147809
129 1236439
130 1331611
131 1433731
132 1543363
133 1660969
134 1787137
135 1922395
136 2067453
137 2222925
138 2389613
139 2568199
140 2759545
141 2964453
142 3183941
143 3418925
144 3670531
145 3939767
146 4227893
147 4536117
148 4865885
149 5218547
150 5595705
151 5998847
152 6429821
153 6890385
154 7382581
155 7908375
156 8470045
157 9069809
158 9710305
159 10394085
160 11124053
161 11903049
162 12734355
163 13621197
164 14567331
165 15576391
166 16652501
167 17799785
168 19022897
169 20326533
170 21715969
171 23196413
172 24773747
173 26453877
174 28243421
175 30149061
176 32178227
177 34338349
178 36637735
179 39084853
180 41689015
181 44459723
182 47407419
183 50542673
184 53877237
185 57423063
186 61193239
187 65201169
188 69461483
189 73989187
190 78800743
191 83912997
192 89344289
193 95113471
194 101241037
195 107748115
196 114657685
197 121993351
198 129780673
199 138046103
200 146818219
201 156126619
202 166003259
203 176481103
204 187595757
205 199384135
206 211885959
207 225142451
208 239197873
209 254098127
210 269892573
211 286632517
212 304372971
213 323171105
214 343088129
215 364187713
216 386538091
217 410210249
218 435280055
219 461826535
220 489934021
221 519690505
222 551189907
223 584530121
224 619815507
225 657154897
226 696664225
227 738464571
228 782684813
229 829459439
230 878931487
231 931250357
232 986574859
233 1045071027
234 1106915137
235 1172291373
236 1241395297
237 1314431289
238 1391616235
239 1473177001
240 1559353937
241 1650398467
242 1746577059
243 1848168445
244 1955467915
245 2068784421
246 2188444829
247 2314791325
248 2448185961
249 2589007685
250 2737657209
251 2894553989
252 3060141285
253 3234883321
254 3419270639
255 3613816731
256 3819063981
257 4035580257
258 4263964995
259 4504846229
260 4758886527
261 5026779733
262 5309257871
263 5607087507
264 5921077149
265 6252073719
266 6600969883
267 6968700591
268 7356251195
269 7764653833
270 8194995803
271 8648416165
272 9126114309
273 9629346585
274 10159435935
275 10717768025
276 11305801429
277 11925063947
278 12577163069
279 13263782753
280 13986694503
281 14747753809
282 15548912149
283 16392213461
284 17279806813
285 18213943207
286 19196988947
287 20231422277
288 21319847763
289 22464993145
290 23669724405
291 24937043149
292 26270102409
293 27672203987
294 29146815631
295 30697568559
296 32328275735
297 34042929735
298 35845721971
299 37741041019
300 39733493079
301 41827900753
302 44029324909
303 46343063741
304 48774676077
305 51329981051
306 54015083041
307 56836371841
308 59800549349
309 62914630191
310 66185970069
311 69622267701
312 73231594707
313 77022398359
314 81003533745
315 85184267027
316 89574310233
317 94183825765
318 99023463121
319 104104364829
320 109438205547
321 115037199231
322 120914141355
323 127082417573
324 133556048423
325 140349699857
326 147478731291
327 154959207607
328 162807951177
329 171042555709
330 179681441261
331 188743871147
332 198250010679
333 208220946077
334 218678748341
335 229646494319
336 241148334783
337 253209519417
338 265856469345
339 279116805343
340 293019426125
341 307594539695
342 322873747235
343 338890079175
344 355678084851
345 373273872579
346 391715206691
347 411041551889
348 431294177357
349 452516207335
350 474752731951
351 498050863811
352 522459857717
353 548031172577
354 574818600761
355 602878337173
356 632269117591
357 663052295563
358 695291991527
359 729055177589
360 764411837903
361 801435063113
362 840201221877
363 880790065547
364 923284913385
365 967772766881
366 1014344509809
367 1063095034273
368 1114123455323
369 1167533250577
370 1223432490937
371 1281933994001
372 1343155572637
373 1407220203385
374 1474256294127
375 1544397868969
376 1617784856711
377 1694563293111
378 1774885631931
379 1858910966807
380 1946805365741
381 2038742114747
382 2134902077911
383 2235473963891
384 2340654714109
385 2450649793781
386 2565673610443
387 2685949832059
388 2811711837905
389 2943203066267
390 3080677499809
391 3224400045671
392 3374647058557
393 3531706755039
394 3695879777747
395 3867479647013
396 4046833368503
397 4234281925875
398 4430180935987
399 4634901185059
400 4848829335103
401 5072368507991
402 5305939046251
403 5549979149767
404 5804945695881
405 6071314930771
406 6349583354505
407 6640268472823
408 6943909750507
409 7261069429967
410 7592333557961
411 7938312874625
412 8299643921433
413 8676990006543
414 9071042398577
415 9482521376153
416 9912177513659
417 10360792819691
418 10829182124969
419 11318194316747
420 11828713833937
421 12361662008287
422 12917998674171
423 13498723622957
424 14104878340191
425 14737547580231
426 15397861238841
427 16086996061379
428 16806177659077
429 17556682360233
430 18339839384403
431 19157032846253
432 20009704098579
433 20899353904083
434 21827544958339
435 22795904241367
436 23806125737971
437 24859972980503
438 25959281981137
439 27105963984615
440 28302008624587
441 29549486903737
442 30850554594657
443 32207455461235
444 33622524924071
445 35098193543361
446 36636990966565
447 38241549694917
448 39914609335783
449 41659020672021
450 43477750242809
451 45373884742057
452 47350635950085
453 49411345487043
454 51559490124079
455 53798686915811
456 56132698921793
457 58565440748637
458 61100984709835
459 63743566811007
460 66497593380501
461 69367647530965
462 72358496298153
463 75475097614669
464 78722607994949
465 82106390059843
466 85632020809457
467 89305299741659
468 93132257756177
469 97119165911765
470 101272545008569
471 105599175032719
472 110106105468567
473 114800665483291
474 119690475022567
475 124783455790669
476 130087843189341
477 135612198152569
478 141365419992633
479 147356759155041
480 153595831035545
481 160092629726397
482 166857542877937
483 173901366507741
484 181235320987263
485 188871066993269
486 196820722699351
487 205096880959155
488 213712627792277
489 222681560886877
490 232017809479849
491 241736054277161
492 251851548825807
493 262380140962937
494 273338295789539
495 284743118756471
496 296612380364073
497 308964541004193
498 321818777508369
499 335195009883679
500 349113929841031
501 363597029560831
502 378666632353323
503 394345923599775
504 410658983698503
505 427630821348489
506 445287408943405
507 463655718367273
508 482763759022227
509 502640616314911
510 523316492508219
511 544822748104147
512 567191945716479
513 590457894560263
514 614655697573607
515 639821799232237
516 665994036157527
517 693211688504399
518 721515534299085
519 750947904663005
520 781552742155063
521 813375660102927
522 846464005240521
523 880866921448203
524 916635416988039
525 953822432973997
526 992482915541003
527 1032673889379467
528 1074454535194877
529 1117886268674919
530 1163032823612057
531 1209960336700073
532 1258737436726031
533 1309435335608233
534 1362127924096153
535 1416891869496637
536 1473806718343533
537 1532955001295033
538 1594422343269289
539 1658297576022313
540 1724672856282243
541 1793643786557147
542 1865309541835021
543 1939772999209403
544 2017140873752285
545 2097523857581187
546 2181036765557193
547 2267798684465267
548 2357933129231503
549 2451568202932983
550 2548836764276773
551 2649876599207757
552 2754830600441689
553 2863846951492481
554 2977079319109343
555 3094687050593953
556 3216835380052785
557 3343695639941811
558 3475445482099877
559 3612269104526711
560 3754357488231739
561 3901908640309309
562 4055127847717511
563 4214227937794789
564 4379429550145609
565 4550961415823599
566 4729060648587243
567 4913973044047869
568 5105953391655871
569 5305265795204705
570 5512184006981015
571 5726991771124541
572 5949983181477669
573 6181463049385839
574 6421747286905029
575 6671163300731725
576 6930050402519249
577 7198760230763011
578 7477657190093717
579 7767118903050357
580 8067536680365217
581 8379316004681213
582 8702877033963165
583 9038655119381439
584 9387101344120883
585 9748683077781829
586 10123884553037549
587 10513207459053215
588 10917171558590689
589 11336315323143111
590 11771196593247079
591 12222393258197657
592 12690503962540437
593 13176148833407487
594 13679970236353117
595 14202633553581503
596 14744827992481277
597 15307267418227357
598 15890691218618803
599 16495865194750831
600 17123582485996435
601 17774664522715327
602 18449962015455903
603 19150355973929975
604 19876758764804383
605 20630115201428243
606 21411403674877457
607 22221637319241559
608 23061865220867995
609 23933173664335183
610 24836687425190531
611 25773571102059719
612 26745030498525205
613 27752314047193547
614 28796714286718373
615 29879569384035919
616 31002264712947031
617 32166234481125933
618 33372963417097879
619 34623988509071475
620 35920900807585937
621 37265347283686749
622 38659032755003621
623 40103721871272213
624 41601241172112969
625 43153481208430417
626 44762398740705543
627 46430019005364599
628 48158438062975789
629 49949825219268029
630 51806425533230539
631 53730562403108375
632 55724640245056405
633 57791147255100529
634 59932658269701419
635 62151837715384123
636 64451442663298439
637 66834325978996673
638 69303439583862017
639 71861837818306789
640 74512680923788011
641 77259238633566461
642 80104893889901621
643 83053146677446391
644 86107617991158131
645 89272053928351053
646 92550329923894673
647 95946455117988589
648 99464576876258565
649 103108985451445573
650 106884118807142655
651 110794567592736583
652 114845080290771045
653 119040568525718637
654 123386112556214487
655 127886966939593515
656 132548566391594077
657 137376531829978477
658 142376676625797833
659 147555013050898525
660 152917758946351735
661 158471344600278565
662 164222419860671947
663 170177861471639623
664 176344780659634017
665 182730530957980791
666 189342716297362941
667 196189199350463611
668 203278110159485813
669 210617855034745641
670 218217125754149005
671 226084909051692315
672 234230496426022299
673 242663494257136951
674 251393834263477697
675 260431784287542505
676 269787959443512433
677 279473333615031077
678 289499251338021255
679 299877440056676071
680 310620022788906245
681 321739531189493209
682 333248919048651139
683 345161576214345113
684 357491342977639147
685 370252524909502959
686 383459908189962771
687 397128775418211217
688 411274921946201417
689 425914672724539289
690 441064899704984879
691 456743039788565795
692 472967113365458865
693 489755743435942659
694 507128175360459325
695 525104297228416857
696 543704660895803369
697 562950503681571249
698 582863770774986857
699 603467138344330153
700 624784037401320359
701 646838678412131853
702 669656076711697977
703 693262078712679149
704 717683388968210387
705 742947598080417317
706 769083211516340535
707 796119679323904831
708 824087426812257759
709 853017886189828481
710 882943529227220227
711 913897900939111455
712 945915654355195577
713 979032586375217299
714 1013285674781217143
715 1048713116403028907
716 1085354366513336503
717 1123250179449435377
718 1162442650541388851
719 1202975259344868587
720 1244892914261947749
721 1288241998549429003
722 1333070417801657071
723 1379427648908849495
724 1427364790581787357
725 1476934615445399681
726 1528191623796229371
727 1581192099027973911
728 1635994164824346107
729 1692657844125314731
730 1751245119970480829
731 1811819998227563863
732 1874448572314567449
733 1939199089925704569
734 2006142021874586743
735 2075350133067131687
736 2146898555722912543
737 2220864864859830345
738 2297329156166427863
739 2376374126279366965
740 2458085155596124275
741 2542550393643417109
742 2629860847137448691
743 2720110470759553867
744 2813396260789824069
745 2909818351625586417
746 3009480115334010851
747 3112488264269417371
748 3218952956911563091
749 3328987906959327359
750 3442710495843607997
751 3560241888697939173
752 3681707153958440969
753 3807235386636179125
754 3936959835441688951
755 4071018033809517309
756 4209551935011297787
757 4352708051410249033
758 4500637598054731723
759 4653496640669331133
760 4811446248250598629
761 4974652650331820097
762 5143287399134116263
763 5317527536674450951
764 5497555767058485321
765 5683560634035667555
766 5875736704055592273
767 6074284754910238555
768 6279411970212958863
769 6491332139806435001
770 6710265866362899211
771 6936440778277114471
772 7170091749128373745
773 7411461123820830907
774 7660798951692202377
775 7918363226709454699
776 8184420135056022583
777 8459244310239195333
778 8743119096037408045
779 9036336817426755093
780 9339199059822547261
781 9652016956786551997
782 9975111486552666453
783 10308813777533802781
784 10653465423180511793
785 11009418806367039257
786 11377037433694148065
787 11756696279898102759
788 12148782142774933117
789 12553694008824034783
790 12971843430041041213
791 13403654912079596827
792 13849566314233947117
793 14310029261478547747
794 14785509569039716541
795 15276487679753214651
796 15783459114707160293
797 16306934937442871025
798 16847442232238798803
799 17405524596770089787
800 17981742649695961245
801 18576674553488714431
802 19190916553085107875
803 19825083530696377951
804 20479809577387809853
805 21155748581788083273
806 21853574836570943951
807 22573983663094962443
808 23317692054877346429
809 24085439340314504671
810 24877987865360707143
811 25696123696606192567
812 26540657345503139101
813 27412424514211457187
814 28312286863851938019
815 29241132805670980709
816 30199878315945884649
817 31189467775169176595
818 32210874832384430073
819 33265103295248633765
820 34353188046739375857
821 35476195989120486403
822 36635227016132981431
823 37831415014065820779
824 39065928892724304381
825 40339973646994276059
826 41654791450073648549
827 43011662779115464091
828 44411907574410937637
829 45856886432905414471
830 47348001837235501933
831 48886699421132300341
832 50474469272441912149
833 52112847274663060657
834 53803416488319702271
835 55547808573126474625
836 57347705252335045219
837 59204839820281002085
838 61120998694593167203
839 63098023014150319903
840 65137810284325356361
841 67242316070670910011
842 69413555742668749601
843 71653606268770401029
844 73964608064437875803
845 76348766894489623187
846 78808355831552187217
847 81345717272004680825
848 83963265011313105581
849 86663486380228717953
850 89448944443849041483
851 92322280265107911303
852 95286215234800480915
853 98343553469806943797
854 101497184281734083051
855 104750084717741635993
856 108105322175891769343
857 111566057096897877443
858 115135545734736869879
859 118817143008116574473
860 122614305435395111897
861 126530594155066169789
862 130569678034546811593
863 134735336869511090179
864 139031464676653643239
865 143462073082263254229
866 148031294809646109839
867 152743387267923442779
868 157602736245407254917
869 162613859710231779857
870 167781411721617387133
871 173110186454606334061
872 178605122341829364961
873 184271306335313715155
874 190113978292083764507
875 196138535486745666277
876 202350537255010063849
877 208755709771535339273
878 215359950966259218145
879 222169335582803374731
880 229190120383344213399
881 236428749503747966233
882 243891859963601098087
883 251586287335159817459
884 259519071576100146695
885 267697463030331068017
886 276128928602016320149
887 284821158107319274245
888 293782070809295225527
889 303019822140711721269
890 312542810620514797583
891 322359684969003345323
892 332479351427738921491
893 342910981289550327903
894 353664018644986924677
895 364748188350893767969
896 376173504227806526637
897 387950277492171126001
898 400089125430448627421
899 412600980321460380375
900 425497098614416642177
901 438789070369353308299
902 452488828967822960569
903 466608661100955696173
904 481161217043160596389
905 496159521218995590973
906 511616983071924791561
907 527547408242926087169
908 543965010068140185453
909 560884421403983781939
910 578320706789415364609
911 596289374954261549011
912 614806391683817197729
913 633888193049139066547
914 653551699013799080977
915 673814327427057795917
916 694694008414806475567
917 716209199178808909829
918 738378899216205713007
919 761222665970413973383
920 784760630926032226679
921 809013516159519231841
922 834002651358938183717
923 859749991325205389277
924 886278133968853938643
925 913610338815458480701
926 941770546034489169015
927 970783396005487339715
928 1000674249437128830319
929 1031469208053854973475
930 1063195135866478304771
931 1095879681042273396697
932 1129551298391846081425
933 1164239272489167777299
934 1199973741443001653193
935 1236785721337031601179
936 1274707131357904663439
937 1313770819629472373831
938 1354010589773478280955
939 1395461228216005179111
940 1438158532261021164481
941 1482139338951422232047
942 1527441554740061087207
943 1574104185992302942457
944 1622167370343810024653
945 1671672408936301122393
946 1722661799556264624765
947 1775179270700642336423
948 1829269816595807730093
949 1884979733195195811279
950 1942356655183325096183
951 2001449594012981807039
952 2062308977004799094315
953 2124986687537490656117
954 2189536106359543782921
955 2256012154052201017959
956 2324471334676191172205
957 2394971780633693940497
958 2467573298779742704331
959 2542337417816293840703
960 2619327437005004141473
961 2698608476233782883973
962 2780247527475094385471
963 2864313507673015339293
964 2950877313099059747239
965 3040011875215817332625
966 3131792218090563976143
967 3226295517400041342105
968 3323601161070823279519
969 3423790811598733662677
970 3526948470094111970379
971 3633160542098779902461
972 3742515905224010742557
973 3855105978657871303435
974 3971024794593875670461
975 4090369071631972623979
976 4213238290206582811537
977 4339734770095500850093
978 4469963750067302965613
979 4604033469724017633137
980 4742055253599778227589
981 4884143597575315480617
982 5030416257672249273207
983 5180994341290302644519
984 5336002400954810010299
985 5495568530641081018739
986 5659824464746583906517
987 5828905679781132290307
988 6002951498849819795111
989 6182105199002701118067
990 6366514121529944449741
991 6556329785280470555883
992 6751708003086992864707
993 6952809001379704703451
994 7159797543075937046279
995 7372843053832487605397
996 7592119751752586246453
997 7817806780638887393021
998 8050088346889339353405
999 8289153860132260150615
1000 8535198077702610117609