0 1
1 1
2 1
3 1
4 3
5 2
6 2
7 5
8 6
9 7
10 7
11 9
12 12
13 13
14 16
15 20
16 25
17 27
18 31
19 38
20 44
21 51
22 58
23 69
24 80
25 92
26 102
27 118
28 141
29 157
30 177
31 203
32 234
33 261
34 292
35 336
36 382
37 428
38 475
39 540
40 610
41 677
42 757
43 852
44 957
45 1060
46 1179
47 1318
48 1470
49 1634
50 1806
51 2011
52 2236
53 2469
54 2724
55 3020
56 3350
57 3689
58 4062
59 4483
60 4953
61 5440
62 5970
63 6584
64 7246
65 7942
66 8695
67 9555
68 10482
69 11461
70 12541
71 13734
72 15034
73 16407
74 17903
75 19560
76 21358
77 23277
78 25348
79 27641
80 30111
81 32752
82 35602
83 38730
84 42135
85 45744
86 49643
87 53907
88 58527
89 63432
90 68724
91 74525
92 80756
93 87402
94 94554
95 102348
96 110728
97 119663
98 129294
99 139728
100 150955
101 162901
102 175764
103 189678
104 204606
105 220556
106 237652
107 256116
108 275911
109 297036
110 319658
111 344044
112 370216
113 398063
114 427897
115 459983
116 494349
117 530937
118 570084
119 612172
120 657144
121 705044
122 756205
123 811121
124 869774
125 932178
126 998875
127 1070280
128 1146489
129 1227545
130 1314066
131 1406580
132 1505240
133 1610214
134 1722054
135 1841567
136 1968886
137 2104236
138 2248370
139 2402198
140 2566034
141 2740019
142 2925211
143 3122598
144 3332653
145 3555643
146 3792758
147 4045401
148 4313922
149 4598865
150 4901640
151 5223900
152 5566176
153 5929203
154 6314821
155 6724708
156 7159867
157 7621127
158 8110683
159 8630704
160 9182376
161 9766977
162 10386890
163 11044943
164 11742533
165 12481363
166 13264378
167 14094874
168 14974953
169 15906386
170 16892970
171 17938630
172 19046000
173 20217405
174 21457450
175 22771085
176 24161132
177 25631017
178 27186066
179 28832214
180 30573264
181 32413353
182 34359199
183 36417532
184 38593459
185 40891959
186 43321218
187 45889454
188 48602862
189 51468135
190 54494518
191 57692284
192 61069056
193 64633092
194 68395634
195 72369046
196 76563132
197 80987376
198 85655982
199 90583523
200 95782011
201 101263535
202 107044952
203 113144199
204 119575454
205 126354104
206 133500108
207 141035173
208 148976844
209 157343782
210 166160663
211 175452620
212 185241747
213 195550744
214 206409189
215 217847418
216 229892366
217 242572325
218 255921708
219 269977858
220 284773186
221 300342028
222 316726188
223 333970092
224 352113741
225 371198000
226 391273704
227 412393612
228 434606467
229 457962068
230 482520972
231 508347321
232 535498750
233 564036474
234 594032733
235 625564134
236 658700630
237 693516144
238 730097851
239 768535746
240 808915581
241 851325967
242 895870896
243 942658532
244 991791724
245 1043378059
246 1097540376
247 1154408808
248 1214106351
249 1276762701
250 1342524652
251 1411546848
252 1483978455
253 1559973171
254 1639707231
255 1723364499
256 1811123628
257 1903169323
258 1999711288
259 2100969474
260 2207155566
261 2318492599
262 2435229181
263 2557626651
264 2685939072
265 2820432448
266 2961403485
267 3109160762
268 3264009237
269 3426265479
270 3596282244
271 3774426272
272 3961060478
273 4156564388
274 4361353690
275 4575865147
276 4800530556
277 5035801572
278 5282171544
279 5540157882
280 5810275775
281 6093059301
282 6389095457
283 6698995620
284 7023371679
285 7362859369
286 7718152462
287 8089975986
288 8479053292
289 8886141038
290 9312058076
291 9757661917
292 10223810754
293 10711400313
294 11221400849
295 11754821098
296 12312679764
297 12896036722
298 13506036828
299 14143871212
300 14810744640
301 15507912761
302 16236721484
303 16998578883
304 17794906831
305 18627188496
306 19497011652
307 20406033878
308 21355936137
309 22348464985
310 23385493105
311 24468969702
312 25600877748
313 26783277547
314 28018370820
315 29308454044
316 30655857970
317 32063012986
318 33532506314
319 35067036373
320 36669347544
321 38342299640
322 40088934619
323 41912415150
324 43815973649
325 45802970028
326 47876974122
327 50041699358
328 52300941600
329 54658651198
330 57119009146
331 59686373651
332 62365197873
333 65160118820
334 68076037320
335 71118057352
336 74291406883
337 77601515855
338 81054127642
339 84655215983
340 88410906534
341 92327562447
342 96411903376
343 100670921616
344 105111780896
345 109741937270
346 114569243893
347 119601873792
348 124848210978
349 130316974140
350 136017343224
351 141958857402
352 148151322971
353 154604926275
354 161330385781
355 168338837768
356 175641733526
357 183250975943
358 191179059384
359 199438979844
360 208044100133
361 217008309159
362 226346174918
363 236072844464
364 246203907631
365 256755547694
366 267744745890
367 279189140507
368 291106898163
369 303516879365
370 316438850098
371 329893347248
372 343901515294
373 358485321444
374 373667756487
375 389472709770
376 405924788218
377 423049546248
378 440873722570
379 459425071982
380 478732216797
381 498824864285
382 519734079324
383 541492104984
384 564132198984
385 587688883637
386 612198211638
387 637697625283
388 664225737331
389 691822627407
390 720530133570
391 750391688274
392 781452106725
393 813757876380
394 847357521745
395 882301390092
396 918641452391
397 956431611664
398 995728094520
399 1036589247383
400 1079075278650
401 1123248657465
402 1169174495370
403 1216920350442
404 1266555954486
405 1318153640916
406 1371788778967
407 1427539525108
408 1485486601790
409 1545713705269
410 1608308010957
411 1673359912906
412 1740962772328
413 1811213393103
414 1884212528184
415 1960064667971
416 2038877721914
417 2120763574012
418 2205838625604
419 2294223566680
420 2386043072860
421 2481426350026
422 2580507810630
423 2683426775249
424 2790327181980
425 2901358184641
426 3016674881308
427 3136438026323
428 3260813671764
429 3389973913350
430 3524097607489
431 3663370114722
432 3807982927668
433 3958134462852
434 4114030884619
435 4275885781494
436 4443919864406
437 4618361760721
438 4799448963480
439 4987427484710
440 5182551534936
441 5385084438176
442 5595299587204
443 5813480197554
444 6039918900974
445 6274918783986
446 6518794437834
447 6771871700302
448 7034487270462
449 7306989773976
450 7589741033812
451 7883115711240
452 8187500971530
453 8503297656095
454 8830921643380
455 9170803540017
456 9523388267904
457 9889136466483
458 10268525886996
459 10662051153387
460 11070223332466
461 11493571457305
462 11932644116770
463 12388009122914
464 12860253229292
465 13349983699096
466 13857830097365
467 14384443975734
468 14930498592720
469 15496690681508
470 16083742320662
471 16692400797117
472 17323438214697
473 17977653514416
474 18655874534206
475 19358957871724
476 20087788584408
477 20843282305312
478 21626387660616
479 22438086051516
480 23279391473675
481 24151352829048
482 25055056562004
483 25991626566186
484 26962223916148
485 27968049606963
486 29010347316063
487 30090403440081
488 31209546886898
489 32369152072162
490 33570642017658
491 34815488347348
492 36105211358900
493 37441383146994
494 38825631116970
495 40259638078252
496 41745142367572
497 43283941389991
498 44877895349232
499 46528927654877
500 48239024999387
501 50010241375749
502 51844702169298
503 53744604688506
504 55712218473434
505 57749889548009
506 59860045186286
507 62045194439229
508 64307928692961
509 66650926376418
510 69076958192012
511 71588887909805
512 74189672961258
513 76882369921575
514 79670140049726
515 82556250445787
516 85544074875110
517 88637099761175
518 91838930431152
519 95153292372576
520 98584032584068
521 102135125989413
522 105810682482688
523 109614948469230
524 113552308511864
525 117627292566541
526 121844583534568
527 126209019491101
528 130725595477003
529 135399471628152
530 140235981542298
531 145240634918294
532 150419119871134
533 155777311720287
534 161321282613638
535 167057304375785
536 172991851490595
537 179131610857854
538 185483492358478
539 192054632425344
540 198852397378402
541 205884394590795
542 213158483911479
543 220682782081628
544 228465666692362
545 236515788523466
546 244842084377457
547 253453781966600
548 262360405049319
549 271571786813892
550 281098084259655
551 290949783957748
552 301137708042422
553 311673029208339
554 322567286376684
555 333832391908919
556 345480638239023
557 357524714748030
558 369977725166244
559 382853195845124
560 396165083736923
561 409927794832717
562 424156203926023
563 438865663846470
564 454072015001488
565 469791605823428
566 486041314650432
567 502838560656116
568 520201314527916
569 538148121750706
570 556698126505974
571 575871084498192
572 595687375357172
573 616168028453655
574 637334749632644
575 659209935623706
576 681816688986832
577 705178846318982
578 729321008242278
579 754268556014424
580 780047668596578
581 806685354297757
582 834209483711144
583 862648809372768
584 892032984917865
585 922392600596303
586 953759219838280
587 986165401693452
588 1019644723126978
589 1054231818029304
590 1089962418592209
591 1126873380460503
592 1165002708542724
593 1204389600457641
594 1245074492460300
595 1287099088423716
596 1330506388895222
597 1375340740232898
598 1421647885051998
599 1469474995656063
600 1518870707272274
601 1569885172568774
602 1622570118125160
603 1676978882010240
604 1733166452455713
605 1791189527950589
606 1851106580477085
607 1912977898219862
608 1976865629510400
609 2042833850123424
610 2110948632998808
611 2181278097715812
612 2253892459830669
613 2328864106150019
614 2406267672374390
615 2486180099145880
616 2568680688437947
617 2653851186792585
618 2741775872736364
619 2832541619533133
620 2926237959671736
621 3022957177617385
622 3122794406893272
623 3225847701643944
624 3332218109117288
625 3442009773942485
626 3555330045435917
627 3672289559136582
628 3793002318863730
629 3917585812736706
630 4046161133130375
631 4178853068075416
632 4315790195322977
633 4457105010747642
634 4602934062331107
635 4753418053531500
636 4908701949509036
637 5068935120556282
638 5234271490523118
639 5404869654831111
640 5580892999467997
641 5762509861360935
642 5949893693695714
643 6143223198800298
644 6342682463080746
645 6548461134841373
646 6760754609599951
647 6979764178955760
648 7205697183483638
649 7438767210731876
650 7679194301391806
651 7927205117692469
652 8183033114734570
653 8446918762523286
654 8719109774471733
655 8999861297596938
656 9289436105634600
657 9588104846166376
658 9896146295549022
659 10213847572016518
660 10541504354728631
661 10879421157709040
662 11227911614445524
663 11587298717668222
664 11957915065453996
665 12340103167043835
666 12734215758653496
667 13140616074606046
668 13559678122836522
669 13991787026287204
670 14437339374403052
671 14896743527533872
672 15370419927357079
673 15858801475738884
674 16362333927906288
675 16881476232925380
676 17416700883082353
677 17968494335825244
678 18537357451192420
679 19123805874602130
680 19728370427855174
681 20351597580957404
682 20994049937350644
683 21656306664285690
684 22338963931639422
685 23042635436729022
686 23767952945276906
687 24515566772628492
688 25286146277869947
689 26080380446471040
690 26898978493339416
691 27742670402014208
692 28612207478249928
693 29508362999510857
694 30431932884383798
695 31383736298950282
696 32364616275314879
697 33375440435337537
698 34417101735555360
699 35490519145826892
700 36596638342834255
701 37736432513907336
702 38910903188335226
703 40121080994815650
704 41368026438951939
705 42652830797748458
706 43976617043784762
707 45340540693750243
708 46745790676697132
709 48193590331686868
710 49685198433742026
711 51221910144027892
712 52805057980776946
713 54436012928691595
714 56116185581160193
715 57847027200312872
716 59630030805450408
717 61466732404795861
718 63358712266745010
719 65307596104477686
720 67315056291889096
721 69382813234411632
722 71512636780485004
723 73706347547931427
724 75965818279613236
725 78292975369148385
726 80689800430151178
727 83158331776446626
728 85700665937284323
729 88318959351424444
730 91015430114522743
731 93792359628747388
732 96652094295710420
733 99597047399360769
734 102629701047516938
735 105752608013928674
736 108968393624672032
737 112279757854502388
738 115689477481570161
739 119200408143361590
740 122815486440962184
741 126537732268056070
742 130370251206174145
743 134316236814528504
744 138378972980341104
745 142561836503171744
746 146868299757550956
747 151301933245362404
748 155866408214717526
749 160565499532527859
750 165403088639187524
751 170383166396424292
752 175509836002306644
753 180787316183724289
754 186219944477312256
755 191812180400989806
756 197568608702917804
757 203493942903423369
758 209593028942505774
759 215870848707979184
760 222332523655106132
761 228983318739325266
762 235828646464824946
763 242874070813576703
764 250125311271629268
765 257588247199804915
766 265268922323312179
767 273173549106390402
768 281308513233164886
769 289680378457578963
770 298295891587954709
771 307161987350430240
772 316285793378888800
773 325674635593038771
774 335336043731612228
775 345277756760995322
776 355507728424205604
777 366034133210299359
778 376865372488686948
779 388010080528443453
780 399477130663724552
781 411275641917895974
782 423414985807787994
783 435904793033473706
784 448754960333362597
785 461975657827287544
786 475577336568506115
787 489570735972353195
788 503966891436617085
789 518777142484595081
790 534013141137270490
791 549686860168517748
792 565810601566479976
793 582397005568002588
794 599459059935035731
795 617010109125936449
796 635063863692298634
797 653634410292809784
798 672736221978064184
799 692384168368381022
800 712593526094242596
801 733379989889476683
802 754759683991517409
803 776749173439042590
804 799365475659838626
805 822626072765735030
806 846548924179233132
807 871152479178307763
808 896455689749211498
809 922478024211640203
810 949239481206626712
811 976760603612329904
812 1005062492806506257
813 1034166823753934209
814 1064095860506868853
815 1094872471633512913
816 1126520146040793655
817 1159063009683156909
818 1192525842726431724
819 1226934096659501511
820 1262313911833129014
821 1298692135970293456
822 1336096343163247228
823 1374554852846655180
824 1414096749240906494
825 1454751901843382417
826 1496550986461008152
827 1539525506232524652
828 1583707813186970412
829 1629131130917237354
830 1675829577862935636
831 1723838190604287748
832 1773192947747368444
833 1823930795020510359
834 1876089671032239910
835 1929708533085193937
836 1984827383627643978
837 2041487298026628180
838 2099730453065391616
839 2159600155531282598
840 2221140871515129386
841 2284398257127983119
842 2349419190035180778
843 2416251801102386884
844 2484945506841037092
845 2555551043383209219
846 2628120501355847430
847 2702707360916802947
848 2779366527663794100
849 2858154370217469526
850 2939128758774575797
851 3022349103889427601
852 3107876396215398624
853 3195773248056081858
854 3286103935993494690
855 3378934443791679676
856 3474332506381022877
857 3572367655781555650
858 3673111268228447087
859 3776636611633335348
860 3883018894238788842
861 3992335315380238359
862 4104665117557815316
863 4220089638942120510
864 4338692367174632774
865 4460558995466927652
866 4585777480138366886
867 4714438098672829662
868 4846633509212047800
869 4982458812527100730
870 5122011615598215684
871 5265392095785554609
872 5412703066604899038
873 5564050046183994111
874 5719541327486976982
875 5879288049247221792
876 6043404268655866602
877 6212007036981699137
878 6385216477112602146
879 6563155861946430859
880 6745951694711655106
881 6933733792467167142
882 7126635371727058632
883 7324793135055782910
884 7528347359820888589
885 7737441990367175402
886 7952224732549410168
887 8172847149383634912
888 8399464759075826164
889 8632237136772657602
890 8871328018891808814
891 9116905408771878028
892 9369141684911892676
893 9628213713275046066
894 9894302962424188530
895 10167595620167872706
896 10448282713073404490
897 10736560230374686623
898 11032629251026314222
899 11336696072454089346
900 11648972342489013367
901 11969675196065963774
902 12299027395383007706
903 12637257472007530049
904 12984599872468510670
905 13341295109060885176
906 13707589914422074037
907 14083737398346470470
908 14469997208433885078
909 14866635696400027873
910 15273926088547064082
911 15692148658751844496
912 16121590905713406888
913 16562547736316742032
914 17015321653600412244
915 17480222947564682174
916 17957569890665628874
917 18447688939974098595
918 18950914944373973440
919 19467591355005665352
920 19998070440830740223
921 20542713511473649301
922 21101891145593002814
923 21675983422908694314
924 22265380161880547705
925 22870481165276298663
926 23491696471861708080
927 24129446612160636136
928 24784162870464298266
929 25456287555415697485
930 26146274277320118282
931 26854588230041232005
932 27581706479748706524
933 28328118263041538106
934 29094325292415991189
935 29880842066911964262
936 30688196190286305770
937 31516928699385580076
938 32367594400607758723
939 33240762212134962566
940 34137015514490879146
941 35056952512154657877
942 36001186604097674929
943 36970346760762211344
944 37965077910193388844
945 38986041336226305799
946 40033915086442838492
947 41109394387378867834
948 42213192069743437030
949 43346039006801154069
950 44508684563475457520
951 45701897053538664130
952 46926464207824728207
953 48183193656748217214
954 49472913424651596111
955 50796472433109193284
956 52154741016389110516
957 53548611452485384589
958 54978998507132130468
959 56446839987815252532
960 57953097311109820880
961 59498756087035586631
962 61084826717608420140
963 62712345006559102704
964 64382372783676660780
965 66095998547692324219
966 67854338124768480745
967 69658535339361997370
968 71509762701217310586
969 73409222112499741585
970 75358145592100597986
971 77357796013674915552
972 79409467861389914986
973 81514488007642497930
974 83674216509584775912
975 85890047420957693967
976 88163409623302468867
977 90495767681168831241
978 92888622717944971872
979 95343513308656883488
980 97862016394070058357
981 100445748220906476267
982 103096365304754174456
983 105815565411713381592
984 108605088563479826541
985 111466718070877277409
986 114402281592280543388
987 117413652212816150337
988 120502749549238079260
989 123671540885897943288
990 126922042337937691815
991 130256320037533095219
992 133676491348296749096
993 137184726113578155771
994 140783247934641828397
995 144474335474297659788
996 148260323791507644641
997 152143605712867753295
998 156126633236914190634
999 160211918966547988320
1000 164402037575430793138