0 1
1 1
2 1
3 1
4 1
5 2
6 4
7 5
8 5
9 5
10 6
11 9
12 12
13 15
14 16
15 17
16 20
17 26
18 34
19 40
20 44
21 48
22 55
23 68
24 84
25 98
26 108
27 118
28 135
29 161
30 192
31 221
32 244
33 268
34 303
35 354
36 414
37 470
38 519
39 571
40 641
41 737
42 847
43 954
44 1052
45 1156
46 1291
47 1465
48 1664
49 1861
50 2048
51 2248
52 2496
53 2807
54 3158
55 3511
56 3855
57 4224
58 4669
59 5211
60 5818
61 6436
62 7050
63 7709
64 8487
65 9414
66 10444
67 11503
68 12571
69 13718
70 15049
71 16606
72 18326
73 20107
74 21924
75 23876
76 26109
77 28682
78 31511
79 34457
80 37488
81 40743
82 44425
83 48617
84 53204
85 58003
86 62973
87 68307
88 74285
89 81021
90 88367
91 96075
92 104099
93 112706
94 122275
95 132968
96 144588
97 156813
98 169589
99 183280
100 198405
101 215183
102 233360
103 252522
104 272607
105 294113
106 317737
107 343781
108 371925
109 401633
110 432845
111 466235
112 502735
113 542763
114 585914
115 631511
116 679499
117 730784
118 786617
119 847563
120 913124
121 982450
122 1055503
123 1133504
124 1218111
125 1310099
126 1408861
127 1513336
128 1623533
129 1741082
130 1868180
131 2005881
132 2153457
133 2309610
134 2474419
135 2650059
136 2839434
137 3043969
138 3262814
139 3494397
140 3738919
141 3999272
142 4279276
143 4580867
144 4903073
145 5244012
146 5604086
147 5987128
148 6398154
149 6839781
150 7310937
151 7809410
152 8335903
153 8895489
154 9494742
155 10137191
156 10821705
157 11545736
158 12310445
159 13122527
160 13990578
161 14919353
162 15907741
163 16952874
164 18056590
165 19227713
166 20477456
167 21812215
168 23231035
169 24730788
170 26314293
171 27993154
172 29781988
173 31689376
174 33714725
175 35854779
176 38113757
177 40506901
178 43053230
179 45764242
180 48640029
181 51677412
182 54882608
183 58275607
184 61881117
185 65714525
186 69777071
187 74066014
188 78590372
189 83376319
190 88455936
191 93849758
192 99560857
193 105587485
194 111942548
195 118660288
196 125782295
197 133335940
198 141327105
199 149755829
200 158640414
201 168025589
202 177965221
203 188495734
204 199627169
205 211362559
206 223727590
207 236780626
208 250591391
209 265208242
210 280647287
211 296916241
212 314050866
213 332127241
214 351235513
215 371439788
216 392764845
217 415225452
218 438871060
219 463800714
220 490130879
221 517946374
222 547284201
223 578169518
224 610670220
225 644915120
226 681054574
227 719200577
228 759407195
229 801714516
230 846215224
231 893076658
232 942492752
233 994611140
234 1049509433
235 1107248853
236 1167955235
237 1231845725
238 1299170278
239 1370123120
240 1444814106
241 1523333988
242 1605852733
243 1692651811
244 1784053130
245 1880311725
246 1981581259
247 2087993285
248 2199776319
249 2317294794
250 2440962934
251 2571115001
252 2707963794
253 2851696694
254 3002619605
255 3161203842
256 3327981971
257 3503391259
258 3687723863
259 3881242950
260 4084356345
261 4297672875
262 4521876697
263 4757538741
264 5005057057
265 5264796973
266 5537300103
267 5823351991
268 6123830751
269 6439480439
270 6770839752
271 7118410789
272 7482910287
273 7865350590
274 8266857719
275 8688399562
276 9130700726
277 9594445463
278 10080579002
279 10590404369
280 11125364185
281 11686715122
282 12275426546
283 12892424021
284 13538950069
285 14216679822
286 14927459707
287 15672918373
288 16454346170
289 17272986780
290 18130468554
291 19028942285
292 19970768910
293 20958055326
294 21992511250
295 23075798044
296 24210043392
297 25398005331
298 26642699682
299 27946847034
300 29312703232
301 30742475772
302 32238937018
303 33805619215
304 35446370674
305 37164698210
306 38963566534
307 40845894594
308 42815285140
309 44876256094
310 47033712893
311 49292167766
312 51655502772
313 54127560557
314 56713010878
315 59417624926
316 62247648925
317 65208878587
318 68306379766
319 71545190420
320 74931348396
321 78472216201
322 82175738541
323 86049346899
324 90099630555
325 94333169585
326 98757752199
327 103382758687
328 108218282840
329 113273837307
330 118557966863
331 124079235465
332 129847666057
333 135875194040
334 142174629126
335 148758127467
336 155636737737
337 162821569158
338 170325492135
339 178163673180
340 186352350070
341 194907031323
342 203841964189
343 213171514965
344 222912175158
345 233083191759
346 243705124189
347 254797725488
348 266379319667
349 278468430814
350 291086146629
351 304256860272
352 318006572719
353 332360402648
354 347341858861
355 362974760652
356 379286018856
357 396306508203
358 414069072867
359 432605603974
360 451946190625
361 472121380728
362 493165449614
363 515117424680
364 538018745434
365 561909838148
366 586829126507
367 612815690314
368 639913102484
369 668170631480
370 697640499832
371 728373874261
372 760419714667
373 793827897054
374 828653712553
375 864959277373
376 902810324886
377 942271517678
378 983405110194
379 1026274612758
380 1070950061367
381 1117509669169
382 1166036077821
383 1216610883547
384 1269313085378
385 1324223379635
386 1381430325563
387 1441032278369
388 1503133014281
389 1567835346336
390 1635239326736
391 1705447274778
392 1778570983198
393 1854733978954
394 1934066423575
395 2016697676570
396 2102754215568
397 2192365517071
398 2285672470832
399 2382830021573
400 2484001232216
401 2589348631462
402 2699031810918
403 2813214296671
404 2932073364146
405 3055803123080
406 3184607614489
407 3318690755218
408 3458253566104
409 3603502193387
410 3754659346384
411 3911967897383
412 4075682864797
413 4246059740765
414 4423351297965
415 4607816944802
416 4799736041805
417 4999412099475
418 5207163479124
419 5423309858685
420 5648168559633
421 5882065447863
422 6125350423235
423 6378402311794
424 6641618091850
425 6915397218447
426 7200137404585
427 7496247312116
428 7804164553217
429 8124361388333
430 8457332258288
431 8803575648707
432 9163589251563
433 9537884727607
434 9927008609316
435 10331548933438
436 10752120829505
437 11189345561094
438 11643844985087
439 12116258709740
440 12607268346574
441 13117605226722
442 13648033762239
443 14199327250585
444 14772261539603
445 15367634954390
446 15986296411754
447 16629154393189
448 17297157756640
449 17991267834366
450 18712451201190
451 19461702799090
452 20240078504393
453 21048705556765
454 21888760456099
455 22761436820232
456 23667937142642
457 24609499608515
458 25587435790923
459 26603142766981
460 27658077686267
461 28753720782530
462 29891565995744
463 31073152046697
464 32300106037727
465 33574157523589
466 34897109283034
467 36270794798940
468 37697067606314
469 39177837276832
470 40715119813736
471 42311053986064
472 43967867775023
473 45687829546228
474 47473235971811
475 49326453673804
476 51249977431120
477 53246449135294
478 55318619315399
479 57469291124286
480 59701306669921
481 62017595176446
482 64421240169823
483 66915501468960
484 69503771117240
485 72189509192443
486 74976228366929
487 77867549572827
488 80867279501792
489 83979436109897
490 87208198200833
491 90557831941796
492 94032673458331
493 97637193135539
494 101376084959296
495 105254296089615
496 109276969247109
497 113449358675988
498 117776810565399
499 122264837284521
500 126919220313378
501 131746044525829
502 136751632428246
503 141942448154202
504 147325075489512
505 152906303530479
506 158693245203255
507 164693376998612
508 170914463998577
509 177364450311973
510 184051434468736
511 190983768208548
512 198170192873891
513 205619885456423
514 213342373221954
515 221347408802256
516 229644942713490
517 238245237232718
518 247159023276796
519 256397553755480
520 265972506468174
521 275895841852812
522 286179772375305
523 296836893737660
524 307880365228105
525 319323971533406
526 331182012430404
527 343469140955468
528 356200329408251
529 369391020463162
530 383057334401247
531 397216140717084
532 411884932964462
533 427081644847434
534 442824612583817
535 459132748867442
536 476025780877584
537 493524333227872
538 511649786146787
539 530424066703846
540 549869607287126
541 570009545793331
542 590867998865520
543 612470157976581
544 634842128932406
545 658010695130658
546 682003271924836
547 706848136912823
548 732574743484441
549 759213832118253
550 786797248987673
551 815357677802209
552 844928589862962
553 875544508883942
554 907241370652379
555 940056651949517
556 974029165815686
557 1009198758147694
558 1045606253296085
559 1083293758500242
560 1122305076288496
561 1162685853817251
562 1204483352114393
563 1247746103194487
564 1292523851114879
565 1338867901847687
566 1386831595984077
567 1436470481735281
568 1487842055221362
569 1541005373419187
570 1596020990687475
571 1652951360746762
572 1711861378325395
573 1772818579585545
574 1835892850259079
575 1901155989263693
576 1968681640827594
577 2038545756223208
578 2110827214216515
579 2185608053284666
580 2262973144126849
581 2343009698264728
582 2425807196059600
583 2511457916962178
584 2600057650022481
585 2691705962970763
586 2786505835346847
587 2884563105847288
588 2985986396736684
589 3090887722655250
590 3199383304043441
591 3311593878974134
592 3427644292857256
593 3547662877707748
594 3671781373717511
595 3800135628132332
596 3932866526267331
597 4070120352929436
598 4212048334368768
599 4358805942017708
600 4510552812328451
601 4667453548915493
602 4829678787919091
603 4997405616964706
604 5170817064754555
605 5350101321174976
606 5535451656928036
607 5727067344069791
608 5925154874857984
609 6129928447481961
610 6341609398427986
611 6560425330173615
612 6786610032669442
613 7020404539623414
614 7262058522687715
615 7511830854691376
616 7769988979680872
617 8036807938722471
618 8312570295945323
619 8597567350471201
620 8892100730902625
621 9196483048535096
622 9511037199786215
623 9836095279918248
624 10171998517162095
625 10519098663119716
626 10877759816068411
627 11248359178660843
628 11631286287326634
629 12026941803023693
630 12435737457953780
631 12858097650627228
632 13294461530564224
633 13745283877353504
634 14211034251565324
635 14692195650953784
636 15189264475486888
637 15702752357129396
638 16233188543169182
639 16781120916259594
640 17347115061447639
641 17931752775600215
642 18535632057951294
643 19159369209099585
644 19803601555508903
645 20468988633365070
646 21156211166528896
647 21865969416379957
648 22598983206876005
649 23355994332368888
650 24137769671920174
651 24945102563533397
652 25778811688234904
653 26639739247043301
654 27528751031709238
655 28446739186827908
656 29394625769580599
657 30373364345252803
658 31383938773269778
659 32427361197652563
660 33504672177233028
661 34616943854294126
662 35765284023336346
663 36950837983852552
664 38174787225061741
665 39438347216058754
666 40742767612457177
667 42089335891562667
668 43479382002912528
669 44914280520170758
670 46395449222588223
671 47924346671144125
672 49502472512370702
673 51131371649009760
674 52812639555554757
675 54547924777996756
676 56338927411771313
677 58187396450608802
678 60095130212852965
679 62063981126845025
680 64095861806717116
681 66192747956710069
682 68356676747657012
683 70589743926097733
684 72894104393855153
685 75271977699247726
686 77725654982160431
687 80257502348961577
688 82869959152542250
689 85565534850612207
690 88346809775818793
691 91216441437538257
692 94177172461051180
693 97231834509922555
694 100383346478410802
695 103634711089888786
696 106989015902564449
697 110449440542325562
698 114019265778973739
699 117701878085545384
700 121500767756703766
701 125419525241077636
702 129461842436901503
703 133631520994502390
704 137932482693347057
705 142368774742465599
706 146944567844451774
707 151664152259374928
708 156531939455669307
709 161552471641723520
710 166730433631367238
711 172070659006652034
712 177578128154559264
713 183257964065247740
714 189115434416597890
715 195155962518418674
716 201385140881405747
717 207808738383426541
718 214432698315262370
719 221263133922584797
720 228306331018065677
721 235568760549439562
722 243057094118438745
723 250778212314874060
724 258739202819070498
725 266947355705441259
726 275410166694438519
727 284135351587673080
728 293130864019472904
729 302404905149984079
730 311965921885805888
731 321822601973738814
732 331983878026579786
733 342458944105347387
734 353257276027634311
735 364388642642281495
736 375863104246558602
737 387691007512073586
738 399882990444082755
739 412450001433359586
740 425403322493225353
741 438754582374781842
742 452515755279396979
743 466699155675407793
744 481317444380914774
745 496383650456834390
746 511911197799317178
747 527913920396899788
748 544406061461701887
749 561402268216081520
750 578917599324611948
751 596967550056364592
752 615568082722451921
753 634735644425718692
754 654487166763725965
755 674840060689695107
756 695812225561438799
757 717422078066103072
758 739688587065028010
759 762631294243855146
760 786270314575997290
761 810626331392909766
762 835720607367267966
763 861575017768579225
764 888212090360858785
765 915655029427580140
766 943927717226973620
767 973054709443956501
768 1003061248483066797
769 1033973301710077263
770 1065817607143790417
771 1098621701407570603
772 1132413922458758075
773 1167223405639705228
774 1203080099724353610
775 1240014810901027574
776 1278059255109834763
777 1317246090562328635
778 1357608922088045060
779 1399182298056469448
780 1442001729701401905
781 1486103741715514684
782 1531525932211579898
783 1578307010556113390
784 1626486803748264920
785 1676106254549885949
786 1727207444705937833
787 1779833653154532910
788 1834029424736005198
789 1889840614207478819
790 1947314395155097487
791 2006499259747658326
792 2067445046581586505
793 2130203007663765281
794 2194825887160194256
795 2261367972598985174
796 2329885106918552768
797 2400434690353846457
798 2473075713763520688
799 2547868835720033427
800 2624876472782611697
801 2704162859059289498
802 2785794062113951653
803 2869837987605741588
804 2956364419107103508
805 3045445106840008466
806 3137153871179985922
807 3231566671937048932
808 3328761628986577356
809 3428819030415182026
810 3531821380014877516
811 3637853499440045450
812 3747002646904787428
813 3859358597762048815
814 3975013670890977785
815 4094062741260063829
816 4216603296488995759
817 4342735554472903671
818 4472562599529275276
819 4606190476109066733
820 4743728222170704050
821 4885287887257983090
822 5030984599762018673
823 5180936702372936558
824 5335265908270898002
825 5494097410097963622
826 5657559921781335555
827 5825785703444330374
828 5998910641281811009
829 6177074403561208324
830 6360420619841496012
831 6549097007676393210
832 6743255424622637311
833 6943051901563114137
834 7148646737436783422
835 7360204678928031092
836 7577895126145390902
837 7801892279922684068
838 8032375206068820730
839 8269527878989667853
840 8513539293895227349
841 8764603673797279069
842 9022920705595120660
843 9288695711299871873
844 9562139726958393909
845 9843469558822560476
846 10132907916100970953
847 10430683649439377387
848 10737032021953844639
849 11052194908234449944
850 11376420890816500201
851 11709965331571630239
852 12053090528588679998
853 12406065990950668368
854 12769168749938228637
855 13142683590283562484
856 13526903167577753051
857 13922128098058136450
858 14328667143804698121
859 14746837529364216415
860 15176965299132039191
861 15619385586038324981
862 16074442753883122102
863 16542490509280988498
864 17023892120058722681
865 17519020780126551365
866 18028260019949668199
867 18552004018671453660
868 19090657776072235477
869 19644637251119334825
870 20214369619264589124
871 20800293692941080840
872 21402860393075066929
873 22022533111602192852
874 22659787918567793006
875 23315113732534845837
876 23989012623423341709
877 24682000297138593906
878 25394606637269581059
879 26127376126053926749
880 26880868093096119940
881 27655656923826248238
882 28452332415618335475
883 29271500336355190198
884 30113783046834099820
885 30979819989507312098
886 31870267986411442753
887 32785801492968264232
888 33727113016389341480
889 34694913759478453299
890 35689934335846805184
891 36712925337224114074
892 37764657689492887069
893 38845922960404321499
894 39957533850749149417
895 41100324936421540015
896 42275153490364295601
897 43482900140941527028
898 44724469296484450353
899 46000789516989889300
900 47312814090243574590
901 48661521887153114500
902 50047918306434298739
903 51473036038494386001
904 52937935570655058014
905 54443705634641870751
906 55991463881822476157
907 57582357869099800769
908 59217566144754054217
909 60898299134545662514
910 62625799741824614142
911 64401343884645435728
912 66226241286570497118
913 68101836613042758083
914 70029510719560816010
915 72010681679318230204
916 74046805494781125818
917 76139376740619816164
918 78289929489174306328
919 80500038620250295453
920 82771321255979825346
921 85105437952321681020
922 87504093541441989204
923 89969037899392178156
924 92502067028395026250
925 95105024566487024963
926 97779803437065895572
927 100528347230045280244
928 103352651197565056570
929 106254763168525524524
930 109236784813391054441
931 112300873384104031311
932 115449243610512669396
933 118684169300971527539
934 122007984517607134377
935 125423084663508734704
936 128931927959835350981
937 132537037451028916033
938 136241003185131529167
939 140046484068230909800
940 143956209249790629847
941 147972979412577305097
942 152099668496579141675
943 156339226009837359197
944 160694679535193072802
945 165169136878284810564
946 169765787698410713348
947 174487905036231506240
948 179338847324460070026
949 184322061050712676226
950 189441083639577191436
951 194699545939982698247
952 200101174142796384329
953 205649791587085278923
954 211349321103826935153
955 217203788084171990955
956 223217323793017681374
957 229394168248607269634
958 235738672474695179619
959 242255300632798151714
960 248948632752432835009
961 255823368266212279958
962 262884329819479561649
963 270136466603094459574
964 277584856995662350858
965 285234711076894780980
966 293091373806245169936
967 301160329095486943438
968 309447204188569047503
969 317957773517866397239
970 326697961800816839753
971 335673846998400127264
972 344891664013683760159
973 354357809383124556124
974 364078846311831286949
975 374061509134274030083
976 384312706939887689542
977 394839527050948273890
978 405649239323647046736
979 416749301551520636592
980 428147365253952179842
981 439851280834659123142
982 451869101822606116316
983 464209088955416245678
984 476879715178380686234
985 489889671867383988236
986 503247875482979794140
987 516963473534142936932
988 531045849534423645320
989 545504627790717362939
990 560349679210338111725
991 575591128466827245428
992 591239361648572601013
993 607305033151589037963
994 623799071466508703123
995 640732684788319432134
996 658117367758568246691
997 675964909715823068378
998 694287403486873092755
999 713097253351001236956
1000 732407181791449607367