0 1
1 1
2 1
3 1
4 2
5 2
6 3
7 3
8 5
9 6
10 8
11 8
12 12
13 13
14 17
15 19
16 26
17 28
18 37
19 40
20 52
21 58
22 73
23 79
24 102
25 113
26 139
27 154
28 191
29 210
30 258
31 284
32 345
33 384
34 462
35 509
36 614
37 679
38 805
39 893
40 1060
41 1171
42 1382
43 1528
44 1792
45 1988
46 2319
47 2560
48 2986
49 3304
50 3823
51 4231
52 4888
53 5399
54 6219
55 6870
56 7880
57 8713
58 9965
59 10993
60 12557
61 13858
62 15758
63 17391
64 19748
65 21766
66 24661
67 27172
68 30702
69 33834
70 38154
71 41985
72 47281
73 52025
74 58429
75 64272
76 72085
77 79215
78 88704
79 97440
80 108902
81 119599
82 133466
83 146430
84 163217
85 179017
86 199169
87 218352
88 242656
89 265827
90 295051
91 323075
92 358074
93 391938
94 433896
95 474569
96 524838
97 573800
98 633734
99 692540
100 764139
101 834502
102 919855
103 1004092
104 1105570
105 1206304
106 1326970
107 1446957
108 1590327
109 1733381
110 1903182
111 2073424
112 2274672
113 2476758
114 2714917
115 2954776
116 3236031
117 3520401
118 3852499
119 4188770
120 4580558
121 4978235
122 5439400
123 5909039
124 6451934
125 7005509
126 7643817
127 8296059
128 9045373
129 9813098
130 10692387
131 11594322
132 12625218
133 13684554
134 14891244
135 16133999
136 17546097
137 19001878
138 20652659
139 22357098
140 24284474
141 26278164
142 28527347
143 30856044
144 33478639
145 36197412
146 39251524
147 42422548
148 45977723
149 49671889
150 53806649
151 58107723
152 62911527
153 67915002
154 73493104
155 79307046
156 85779299
157 92531369
158 100033437
159 107868285
160 116559745
161 125642065
162 135703553
163 146225693
164 157862897
165 170043783
166 183495955
167 197583743
168 213123078
169 229407244
170 247342153
171 266150724
172 286839688
173 308545836
174 332395023
175 357430448
176 384901434
177 413756634
178 445382057
179 478613158
180 514997793
181 553247097
182 595076059
183 639071287
184 687134130
185 737701462
186 792891979
187 850980331
188 914312561
189 980998209
190 1053634529
191 1130136189
192 1213393770
193 1301109139
194 1396478724
195 1496989209
196 1606176994
197 1721274239
198 1846209531
199 1977939830
200 2120806735
201 2271485843
202 2434774742
203 2607021101
204 2793548422
205 2990347745
206 3203295591
207 3428020481
208 3671011986
209 3927475310
210 4204600400
211 4497136195
212 4813014877
213 5146517723
214 5506395148
215 5886388853
216 6296183841
217 6728938045
218 7195325990
219 7687909893
220 8218458206
221 8778845628
222 9382080912
223 10019300486
224 10704833894
225 11429059680
226 12207761717
227 13030452798
228 13914564767
229 14848678034
230 15851978470
231 16912093994
232 18050145868
233 19252674041
234 20542979505
235 21906438410
236 23368682814
237 24913895508
238 26570272575
239 28320645135
240 30196094774
241 32178005006
242 34300542938
243 36543615104
244 38944786716
245 41482292352
246 44197503645
247 47066876352
248 50135867369
249 53379113717
250 56846560410
251 60510801794
252 64426806413
253 68564995387
254 72985728439
255 77657217512
256 82645751029
257 87917062643
258 93544051876
259 99489833175
260 105834421551
261 112538270113
262 119689204190
263 127244713375
264 135301324497
265 143813399927
266 152886833722
267 162472834971
268 172687586174
269 183478790467
270 194974058464
271 207117423765
272 220048827905
273 233708617503
274 248250256823
275 263610024192
276 279956393085
277 297221401335
278 315589721173
279 334989176605
280 355622211570
281 377412014279
282 400580707091
283 425046700120
284 451053391359
285 478514486972
286 507696699781
287 538508608957
288 571242724699
289 605802389297
290 642508011586
291 681257881557
292 722402988887
293 765836148884
294 811942122410
295 860608242589
296 912255844979
297 966767102522
298 1024603405170
299 1085641417185
300 1150386731918
301 1218710633373
302 1291166601399
303 1367621109387
304 1448680085674
305 1534204956466
306 1624859442949
307 1720500314761
308 1821853972040
309 1928773422034
310 2042053665030
311 2161543962385
312 2288114859979
313 2421612621260
314 2562989744002
315 2712090912208
316 2869958323602
317 3036435464570
318 3212663191838
319 3398485129317
320 3595149253480
321 3802501449371
322 4021906873144
323 4253214682163
324 4497918844694
325 4755873933309
326 5028713807551
327 5316301643605
328 5620424329859
329 5940955545682
330 6279850229948
331 6636995939979
332 7014530244695
333 7412359207082
334 7832820080080
335 8275840713610
336 8743977541678
337 9237185263726
338 9758258554957
339 10307185677490
340 10887021783000
341 11497793904317
342 12142842867501
343 12822241995467
344 13539642789588
345 14295174399046
346 15092827862025
347 15932796193357
348 16819442653237
349 17753034987236
350 18738341311184
351 19775717625480
352 20870374478097
353 22022768060642
354 23238593609032
355 24518423105620
356 25868479170687
357 27289468480326
358 28788189790731
359 30365501941678
360 32028834603476
361 33779220794619
362 35624776746633
363 37566736009701
364 39613964757124
365 41767922086172
366 44038294943905
367 46426798880281
368 48944014248238
369 51591949405715
370 54382160289778
371 57316983565030
372 60409042514402
373 63661044982403
374 67086776107573
375 70689364933657
376 74483865157809
377 78473876686737
378 82675840407715
379 87093886299138
380 91745965528626
381 96636806431990
382 101786008700123
383 107198968049294
384 112897086249015
385 118886507469787
386 125190595484306
387 131816335873993
388 138789233671620
389 146117210849436
390 153828112134623
391 161930906478788
392 170455986173568
393 179413492920997
394 188836598591306
395 198736747670018
396 209150148232838
397 220089697412559
398 231594909131878
399 243680302861041
400 256388998808493
401 269737315513231
402 283772310884592
403 298512304921038
404 314008643027921
405 330281874499261
406 347388020687480
407 365350099366644
408 384229235992783
409 404051188732174
410 424882640152621
411 446752393909848
412 469733191991528
413 493857205427038
414 519203788070327
415 545808842528823
416 573758921107216
417 603094064899241
418 633908673325013
419 666247357580104
420 700213077083955
421 735855498909237
422 773286900892829
423 812562547311451
424 853804871975756
425 897075312526722
426 942507377639375
427 990169324449202
428 1040206716734166
429 1092695348802520
430 1147793919697259
431 1205586527618435
432 1266246191127408
433 1329866168700690
434 1396635063663033
435 1466656244020797
436 1540135290477858
437 1617186697080696
438 1698034546570360
439 1782805591217559
440 1871744048120946
441 1964990179620834
442 2062810130629517
443 2165359017519387
444 2272926875275380
445 2385685166602484
446 2503949919899402
447 2627910591460942
448 2757911511716148
449 2894161901847129
450 3037036917290227
451 3186767506536334
452 3343762358673239
453 3508276311422788
454 3680754556150420
455 3861478148577073
456 4050932024770098
457 4249426032291041
458 4457488336088230
459 4675460407095682
460 4903917454328529
461 5143235625461879
462 5394041336621882
463 5656748780792227
464 5932040059895274
465 6220371112174284
466 6522484623584611
467 6838882272120273
468 7170372669767783
469 7517507632626978
470 7881167449599835
471 8261958900292910
472 8660840235178862
473 9078478410542744
474 9515916486825219
475 9973887328655329
476 10453526185416738
477 10955638110076976
478 11481458596572919
479 12031871675980763
480 12608221860679082
481 13211479613304868
482 13843107922874100
483 14504171841871295
484 15196263154163406
485 15920550326364741
486 16678765167578334
487 17472189233264042
488 18302706471483184
489 19171722104592270
490 20081285423325255
491 21032936763851061
492 22028905123965094
493 23070878487556178
494 24161281058739763
495 25301962161382813
496 26495558089209409
497 27744094326337069
498 29050437612261003
499 30416805801647646
500 31846315894502466
501 33341395808097947
502 34905434370913545
503 36541088717194564
504 38252042943274973
505 40041204328574834
506 41912577544308027
507 43869342838775913
508 45915852988611937
509 48055585923091512
510 50293272427351289
511 52632715087562496
512 55079054991794474
513 57636448778713678
514 60310482948138812
515 63105700022023102
516 66028170030917239
517 69082856094708882
518 72276352946244998
519 75614082105922594
520 79103207745269073
521 82749650718364076
522 86561193183713705
523 90544299935071544
524 94707423561732235
525 99057621336722650
526 103604073231768033
527 108354481557741150
528 113318815449306112
529 118505479483785617
530 123925298698113305
531 129587442173137725
532 135503663289511134
533 141683963014727939
534 148141101621754143
535 154885985283276648
536 161932466022653384
537 169292434902990898
538 176980927758338266
539 185010906807790197
540 193398691480693657
541 202158408950474795
542 211307770037426574
543 220862168755609633
544 230840824209256058
545 241260507535342622
546 252142072770812410
547 263503788012117687
548 275368279043091903
549 287755441015769339
550 300689819751313831
551 314193078252334341
552 328291842987174745
553 343009697706084298
554 358375523010166919
555 374414989299004262
556 391159419266964700
557 408636749472087323
558 426880948199199730
559 445922412992496081
560 465797977522209023
561 486540711608604081
562 508190552337761306
563 530783470381204791
564 554362763858953261
565 578967552235091138
566 604644772878331352
567 631436962808845046
568 659394999824346747
569 688565129184893337
570 719002494963530202
571 750757365808536149
572 783889503925015256
573 818453542802041431
574 854514243524483916
575 892130973640182522
576 931373904908574093
577 972307539023588491
578 1015007903014791791
579 1059545066010938843
580 1106001391236604726
581 1154452983660548664
582 1204989062663739232
583 1257692276379610627
584 1312659261638961800
585 1369979758923125689
586 1429758429442537978
587 1492092699572967582
588 1557095910889531195
589 1624873818224200433
590 1695549151517974318
591 1769236689348249395
592 1846069315320503930
593 1926171583015394662
594 2009687356584055615
595 2096751777546929290
596 2187520582892633289
597 2282140381363594776
598 2380779746946454278
599 2483597705420855870
600 2590776709194550565
601 2702489228432862332
602 2818932717546100869
603 2940294201841834511
604 3066787351406721048
605 3198614946223560932
606 3336008182570967195
607 3479186892020914756
608 3628401210671355883
609 3783889423346700320
610 3945922132425008690
611 4114757589268464772
612 4290688510299894430
613 4473994748892218848
614 4664992912546941838
615 4863986223557017492
616 5071317098761642799
617 5287314036466878153
618 5512347332914052028
619 5746772822699168739
620 5990990913463139227
621 6245387001127384875
622 6510394013334657733
623 6786429308244399587
624 7073960931950889376
625 7373440797623644315
626 7685374870903483964
627 8010252419091919271
628 8348620349171900462
629 8701008302117703027
630 9068007385263538868
631 9450190872895007546
632 9848197585097805966
633 10262647947301095095
634 10694232280313586570
635 11143621954514800831
636 11611562875598435641
637 12098781452888456703
638 12606083577667231202
639 13134255114983579131
640 13684166686260280259
641 14256668374230668553
642 14852700644525149049
643 15473182934523430286
644 16119131063248947182
645 16791539362857767438
646 17491504943638787827
647 18220103003990408870
648 18978518344004658664
649 19767913467833692210
650 20589567756662665168
651 21444737963052154304
652 22334805474655311645
653 23261128773569459491
654 24225199253116116377
655 25228485189751210816
656 26272596595697099779
657 27359120233943296085
658 28489794013706334198
659 29666332548302736224
660 30890611636308221471
661 32164483832448474584
662 33489973581520262340
663 34869082252320136227
664 36303994519802481056
665 37796872276405906917
666 39350072899559371806
667 40965931420390537808
668 42646991342218218920
669 44395774422791927417
670 46215024742795233436
671 48107465416506248689
672 50076056657585105632
673 52123738693119725758
674 54253704607615855507
675 56469128707289389082
676 58773454962342729235
677 61170110020571347077
678 63662808123946974528
679 66255247924344861974
680 68951434790062156848
681 71755360543300336199
682 74671344118198916336
683 77703693284462494122
684 80857064683285649129
685 84136106547853896311
686 87545839190164041261
687 91091277690124187763
688 94777833960109684898
689 98610918310468897920
690 102596364293740525620
691 106740007992263517817
692 111048136898783887004
693 115527045725969643529
694 120183510643213072115
695 125024320334041788802
696 130056776995866686454
697 135288201299330600722
698 140726461622159448841
699 146379451510665673768
700 152255648692671443405
701 158363563556087380172
702 164712329586581193452
703 171311121294968193960
704 178169777800884819028
705 185298188577573187944
706 192706951989190454852
707 200406727123173626287
708 208408929205381867954
709 216725045693990634096
710 225367370585361062244
711 234348282869536077239
712 243681021840682886858
713 253378925900691321187
714 263456251122993669800
715 273927368279631977458
716 284807627011207241436
717 296112508866332599995
718 307858539548453603554
719 320062395625732211139
720 332741867481641119543
721 345914917224922738397
722 359600695092662879248
723 373818545989083839305
724 388589082227565111715
725 403933135976159325513
726 419872891405756255547
727 436430780172111611534
728 453630676179913239674
729 471496731113362062703
730 490054635186735977467
731 509330389561906385698
732 529351636665046233785
733 550146366158589043905
734 571744318570559921680
735 594175621351390693870
736 617472269749956786613
737 641666689285720595774
738 666793298047406375097
739 692886991714101935486
740 719984791647541951320
741 748124248436180400497
742 777345180370854273390
743 807687991255971289193
744 839195504137990775221
745 871911188901072840121
746 905881096345780541637
747 941151990901115394902
748 977773390405827295317
749 1015795599004445352002
750 1055271858307015417923
751 1096256275275815395595
752 1138806090705556638353
753 1182979496692102285483
754 1228838028672277532951
755 1276444266762407513599
756 1325864357970780818552
757 1377165595393624177282
758 1430419077524084392246
759 1485697159043626275428
760 1543076254497346455722
761 1602634154070266891191
762 1664452979331074319313
763 1728616357037889367115
764 1795212535015136518971
765 1864331406744096468271
766 1936067795840371381787
767 2010518323784859308314
768 2087784871968881684697
769 2167971284524996539916
770 2251187017329799886752
771 2337543667559442602388
772 2427158819508719037553
773 2520152392037853421868
774 2616650691643944774197
775 2716782568511031404256
776 2820683687762930023497
777 2928492484441798182749
778 3040354664416538499952
779 3156418948090229912287
780 3276841813105507689234
781 3401783016059832163117
782 3531410589723722192936
783 3665896131596480267706
784 3805420068986965542339
785 3950166702641438296085
786 4100329753807594759283
787 4256107150568923342187
788 4417706871681749218741
789 4585341462735640891769
790 4759234192290022329583
791 4939613284292941261912
792 5126718402934552425464
793 5320794587072562193723
794 5522099080998883499915
795 5730894956027255600290
796 5947458305225498126435
797 6172071536535137609654
798 6405030950550799008803
799 6646639688759397017795
800 6897215714354756561454
801 7157084398501711530196
802 7426586925168680948091
803 7706072497424942557079
804 7995907188462603351635
805 8296465749040976555152
806 8608140927924185946957
807 8931334860802823228033
808 9266468884528485657994
809 9613974486819000440990
810 9974303640044351437685
811 10347919290000650569258
812 10735306236228614759494
813 11136961137241644364630
814 11553403965699214722877
815 11985167506307266534526
816 12432809415754814531714
817 12896901188339562667628
818 13378040852002424633702
819 13876841375699938687358
820 14393944034428167628257
821 14930006231033665958774
822 15485715564950040739621
823 16061777039811164538174
824 16658927872281582643510
825 17277924055654467011044
826 17919555946963858984786
827 18584634155236638073373
828 19274005947190112790590
829 19988540427294602773338
830 20729145804286603907186
831 21496753828848008509079
832 22292337965261402926743
833 23116897050791065616533
834 23971474419250312680910
835 24857140744448809482678
836 25775014164680198467418
837 26726242271057333663185
838 27712023284360480710369
839 28733587147127617636917
840 29792217807125217162321
841 30889233370105013190499
842 32026009546759370234422
843 33203958821296219805044
844 34424555121561832884525
845 35689311956367465534678
846 36999808371721296569625
847 38357666007620434374919
848 39764576406353009101406
849 41222276937464220756691
850 42732579527361080930419
851 44297345398647196299432
852 45918515294026339665410
853 47598082973683050966182
854 49338127009986928724253
855 51140782984315649080250
856 53008276932855275970580
857 54942896181415437209345
858 56947024526967975251826
859 59023111646152978924723
860 61173710101267701679667
861 63401443255571157190015
862 65709044196833617351339
863 68099322089328356520348
864 70575203113072687199773
865 73139695179169953723169
866 75795930987596913712359
867 78547131029620602754009
868 81396648872085889295128
869 84347932366995370315962
870 87404571276050234861388
871 90570256603837992474876
872 93848830681862003343201
873 97244244538453475015958
874 100760610567436181864406
875 104402157843777671712764
876 108173287508734483322967
877 112078525936146806069286
878 116122582972271560485070
879 120310302853861969881803
880 124646725447747729061047
881 129137034817220306727206
882 133786623614158189756537
883 138601039185608664276070
884 143586051278638158547651
885 148747595574753507993918
886 154091844875599739357366
887 159625149947667167756421
888 165354114365899539039072
889 171285532545925180658871
890 177426468431203805067544
891 183784190585234613982071
892 190366254917075689099270
893 197180436700145422443582
894 204234817541278954813055
895 211537714186891947928823
896 219097769950675974211714
897 226923880162511731408691
898 235025288280575527504516
899 243411507831846196046590
900 252092423446332296115998
901 261078209131462206806803
902 270379434477671044931711
903 280006979102924284095605
904 289972144291270840905987
905 300286563436427710171266
906 310962319388702312559901
907 322011850719233271641041
908 333448075064060715894225
909 345284291023854999540128
910 357534307808249131772374
911 370212342577708779197239
912 383333156707188014043812
913 396911948368606969023475
914 410964495748410122011779
915 425507044661562980670349
916 440556459074208852517641
917 456130103530979341677280
918 472246001352381493893309
919 488922711648097626025822
920 506179495576738057834586
921 524036187709386094673486
922 542513370758614197682889
923 561632241046392413568260
924 581414792130582004554473
925 601883674121190529576977
926 623062386653444928694678
927 644975131787020699300531
928 667647016797127172564864
929 691103900380091416193052
930 715372605758539791232153
931 740480759905484616911802
932 766457017483921410180091
933 793330892791199703195688
934 821132995079245741228647
935 849894852908557150325227
936 879649161423773805676207
937 910429598794220889477724
938 942271086047672246692975
939 975209595262919625010937
940 1009282422594592442508542
941 1044527987869506333289777
942 1080986121468389912010784
943 1118697854964089380107540
944 1157705722558685745235987
945 1198053542389036777508984
946 1239786733252580185278244
947 1282952086190606540459733
948 1327598097274213335316360
949 1373774729060687685292965
950 1421533760248948368546730
951 1470928536590616507624503
952 1522014338264656396502872
953 1574848119808184954661348
954 1629488896104199075887263
955 1685997470880758131150727
956 1744436842249642005554107
957 1804871919307486588523638
958 1867369948210047862844231
959 1932000216390843325543870
960 1998834500206838131136823
961 2067946756272273713663761
962 2139413591762617106617754
963 2213313942344924285968848
964 2289729566281222410000442
965 2368744708417182157604714
966 2450446619285319580698329
967 2534925204594397594539754
968 2622273570592071445976208
969 2712587658479820577727380
970 2805966817357699133561060
971 2902513422968464246855540
972 3002333479615677375131321
973 3105536222619854995908455
974 3212234750669948630671212
975 3322545611355473738596562
976 3436589465484549851137920
977 3554490655033280060826776
978 3676377901042987403178948
979 3802383853305833131584365
980 3932645823533761363417042
981 4067305316079296063914483
982 4206508798153615505809422
983 4350407210857303046501722
984 4499156778317043573478407
985 4652918498277462596211873
986 4811858992118712193358038
987 4976149974239445362262228
988 5145969145016131132958818
989 5321499638181686622901289
990 5502930958894080251908766
991 5690458408290309575255357
992 5884284068939626844531218
993 6084616205730632075409272
994 6291670301098912293153223
995 6505668431378343726067153
996 6726840354316666821702026
997 6955422859996306247156920
998 7191660913276628310412969
999 7435806978367150936350553
1000 7688122218968157933735349