0 1
1 1
2 1
3 2
4 2
5 2
6 3
7 4
8 4
9 6
10 8
11 9
12 11
13 14
14 16
15 19
16 23
17 27
18 32
19 38
20 45
21 53
22 62
23 72
24 84
25 97
26 112
27 130
28 150
29 172
30 199
31 228
32 260
33 298
34 340
35 386
36 440
37 500
38 566
39 642
40 727
41 820
42 926
43 1044
44 1174
45 1321
46 1484
47 1664
48 1866
49 2090
50 2337
51 2613
52 2918
53 3254
54 3628
55 4041
56 4495
57 4999
58 5554
59 6164
60 6839
61 7581
62 8395
63 9294
64 10280
65 11361
66 12551
67 13855
68 15282
69 16850
70 18566
71 20441
72 22497
73 24744
74 27196
75 29880
76 32809
77 36002
78 39490
79 43292
80 47432
81 51947
82 56862
83 62208
84 68030
85 74360
86 81237
87 88716
88 96838
89 105652
90 115226
91 125611
92 136869
93 149082
94 162316
95 176648
96 192177
97 208987
98 227174
99 246858
100 268145
101 291153
102 316029
103 342904
104 371926
105 403273
106 437107
107 473611
108 513002
109 555480
110 601271
111 650637
112 703827
113 761116
114 822824
115 889257
116 960751
117 1037694
118 1120462
119 1209466
120 1305175
121 1408049
122 1518590
123 1637364
124 1764934
125 1901911
126 2048978
127 2206820
128 2376180
129 2557882
130 2752759
131 2961710
132 3185730
133 3425828
134 3683092
135 3958721
136 4253934
137 4570046
138 4908498
139 5270764
140 5658429
141 6073222
142 6516922
143 6991436
144 7498838
145 8041270
146 8621022
147 9240580
148 9902516
149 10609580
150 11364746
151 12171098
152 13031932
153 13950802
154 14931402
155 15977675
156 17093862
157 18284382
158 19553944
159 20907606
160 22350645
161 23888678
162 25527728
163 27274088
164 29134450
165 31115979
166 33226166
167 35472976
168 37864920
169 40410908
170 43120405
171 46003510
172 49070806
173 52333526
174 55803642
175 59493709
176 63417039
177 67587810
178 72020896
179 76732060
180 81738071
181 87056529
182 92706078
183 98706528
184 105078684
185 111844571
186 119027567
187 126652237
188 134744570
189 143332132
190 152443891
191 162110481
192 172364371
193 183239686
194 194772498
195 207001013
196 219965387
197 233708051
198 248273916
199 263710190
200 280066733
201 297396283
202 315754285
203 335199268
204 355793106
205 377600851
206 400691141
207 425136501
208 451013178
209 478401594
210 507386678
211 538057711
212 570508835
213 604839412
214 641153894
215 679562378
216 720181009
217 763131875
218 808543614
219 856551874
220 907299228
221 960935843
222 1017620008
223 1077518070
224 1140805182
225 1207665892
226 1278294117
227 1352893978
228 1431680458
229 1514879426
230 1602728562
231 1695478095
232 1793390892
233 1896743478
234 2005826878
235 2120946764
236 2242424593
237 2370598566
238 2505823846
239 2648473828
240 2798941228
241 2957638383
242 3124998682
243 3301477786
244 3487554046
245 3683730094
246 3890534221
247 4108520937
248 4338272736
249 4580401666
250 4835550034
251 5104392381
252 5387637271
253 5686028154
254 6000345598
255 6331409304
256 6680079167
257 7047257793
258 7433892774
259 7840977984
260 8269556401
261 8720722689
262 9195624767
263 9695466970
264 10221512990
265 10775087745
266 11357580931
267 11970450369
268 12615224222
269 13293504994
270 14006973325
271 14757390609
272 15546603513
273 16376548264
274 17249253744
275 18166846579
276 19131555991
277 20145717447
278 21211778378
279 22332303696
280 23509980045
281 24747622249
282 26048179585
283 27414740716
284 28850540976
285 30358969477
286 31943574835
287 33608073402
288 35356357308
289 37192501112
290 39120771077
291 41145634285
292 43271766342
293 45504061828
294 47847644638
295 50307876863
296 52890370583
297 55600999596
298 58445909628
299 61431531660
300 64564595201
301 67852140024
302 71301531220
303 74920474220
304 78717028270
305 82699623417
306 86877077512
307 91258611670
308 95853869422
309 100672935972
310 105726355887
311 111025154700
312 116580860720
313 122405525234
314 128511746898
315 134912696399
316 141622139508
317 148654464632
318 156024710670
319 163748593326
320 171842536175
321 180323702156
322 189210023560
323 198520237052
324 208273919282
325 218491520997
326 229194406534
327 240404894072
328 252146294398
329 264442955450
330 277320307762
331 290804908506
332 304924491720
333 319708019592
334 335185732468
335 351389205454
336 368351406282
337 386106752050
338 404691172984
339 424142177732
340 444498917656
341 465802258658
342 488094854840
343 511421221286
344 535827814972
345 561363117805
346 588077718974
347 616024406078
348 645258258684
349 675836741482
350 707819806843
351 741270000216
352 776252565442
353 812835560132
354 851089974386
355 891089849735
356 932912408932
357 976638189630
358 1022351178620
359 1070138957830
360 1120092854743
361 1172308093840
362 1226883960780
363 1283923971590
364 1343536043448
365 1405832679203
366 1470931157648
367 1538953726004
368 1610027807232
369 1684286213960
370 1761867365277
371 1842915519600
372 1927581015114
373 2016020513816
374 2108397263032
375 2204881365517
376 2305650054059
377 2410887985092
378 2520787541992
379 2635549143944
380 2755381575451
381 2880502326805
382 3011137941344
383 3147524385100
384 3289907428920
385 3438543038643
386 3593697789675
387 3755649295720
388 3924686646964
389 4101110874934
390 4285235433293
391 4477386689769
392 4677904447227
393 4887142482650
394 5105469099216
395 5333267710131
396 5570937442675
397 5818893757509
398 6077569102630
399 6347413590128
400 6628895690575
401 6922502965325
402 7228742824489
403 7548143305178
404 7881253891310
405 8228646362219
406 8590915664559
407 8968680829793
408 9362585923950
409 9773301024120
410 10201523244885
411 10647977800957
412 11113419100415
413 11598631892626
414 12104432456840
415 12631669825603
416 13181227068191
417 13754022619663
418 14351011649430
419 14973187495800
420 15621583151549
421 16297272794337
422 17001373389689
423 17735046350954
424 18499499250154
425 19295987608548
426 20125816750917
427 20990343717447
428 21890979263192
429 22829189928846
430 23806500176458
431 24824494621543
432 25884820344887
433 26989189277480
434 28139380691634
435 29337243781002
436 30584700322969
437 31883747457993
438 33236460568066
439 34644996247886
440 36111595404790
441 37638586469231
442 39228388709464
443 40883515688014
444 42606578841432
445 44400291176938
446 46267471125333
447 48211046531334
448 50234058774840
449 52339667064552
450 54531152884590
451 56811924587737
452 59185522178810
453 61655622268232
454 64226043189784
455 66900750327954
456 69683861634695
457 72579653329838
458 75592565832550
459 78727209903592
460 81988372992686
461 85381025840781
462 88910329316754
463 92581641483000
464 96400524942360
465 100372754445508
466 104504324753743
467 108801458812270
468 113270616212744
469 117918501940674
470 122752075465376
471 127778560151217
472 133005452986316
473 138440534689158
474 144091880172022
475 149967869357856
476 156077198414213
477 162428891383287
478 169032312205210
479 175897177201716
480 183033567999200
481 190451944889255
482 198163160697353
483 206178475138736
484 214509569660814
485 223168562846296
486 232168026356509
487 241521001415449
488 251241015912528
489 261342102104184
490 271838814916008
491 282746250927663
492 294080068021489
493 305856505697642
494 318092406142856
495 330805236034301
496 344013109083125
497 357734809409687
498 371989815732684
499 386798326378936
500 402181285210723
501 418160408454219
502 434758212437951
503 451998042343466
504 469904101953422
505 488501484408221
506 507816204079381
507 527875229546561
508 548706517691862
509 570339049026162
510 592802864236149
511 616129101968779
512 640350037974789
513 665499125601970
514 691611037658520
515 718721709775243
516 746868385259961
517 776089661468353
518 806425537827512
519 837917465508926
520 870608398779069
521 904542848172359
522 939766935486783
523 976328450634762
524 1014276910503360
525 1053663619827817
526 1094541734116321
527 1136966324789953
528 1180994446545910
529 1226685206988110
530 1274099838699297
531 1323301773767915
532 1374356720820398
533 1427332744744010
534 1482300349119514
535 1539332561421193
536 1598505021181685
537 1659896071147396
538 1723586851489654
539 1789661397282534
540 1858206739280055
541 1929313008066839
542 2003073541807402
543 2079584997634580
544 2158947466761242
545 2241264593555505
546 2326643698629093
547 2415195906033878
548 2507036274823076
549 2602283935037112
550 2701062228220879
551 2803498852746868
552 2909726014015524
553 3019880579652380
554 3134104239996182
555 3252543673961617
556 3375350720410764
557 3502682555348648
558 3634701875040036
559 3771577085198004
560 3913482496582057
561 4060598527118536
562 4213111910711640
563 4371215913107038
564 4535110554938406
565 4705002842144343
566 4881107004144440
567 5063644739923968
568 5252845472235712
569 5448946610337074
570 5652193821432563
571 5862841311054012
572 6081152112828098
573 6307398387824192
574 6541861733741262
575 6784833504417101
576 7036615139878828
577 7297518507221982
578 7567866252838126
579 7847992166238706
580 8138241555793561
581 8438971636944224
582 8750551933171298
583 9073364690068410
584 9407805303126798
585 9754282759544167
586 10113220094448296
587 10485054862186922
588 10870239623035238
589 11269242445753586
590 11682547426697896
591 12110655225876332
592 12554083620430614
593 13013368076299930
594 13489062338507658
595 13981739040599074
596 14491990334048856
597 15020428538129642
598 15567686810824302
599 16134419841667254
600 16721304567061656
601 17329040908715554
602 17958352536154216
603 18609987653916562
604 19284719814145354
605 19983348755605928
606 20706701269809210
607 21455632095021208
608 22231024839278120
609 23033792933157558
610 23864880613166977
611 24725263936960934
612 25615951831219240
613 26537987173133546
614 27492447906814876
615 28480448195543123
616 29503139610901342
617 30561712360216728
618 31657396553326870
619 32791463509818660
620 33965227108280237
621 35180045178692162
622 36437320939219290
623 37738504479072490
624 39085094288684764
625 40478638838587419
626 41920738208796236
627 43413045770081490
628 44957269918643184
629 46555175866155116
630 48208587486692475
631 49919389222213556
632 51689528048726030
633 53521015504806506
634 55415929784307614
635 57376417895563779
636 59404697888933964
637 61503061154693828
638 63673874793785220
639 65919584063447156
640 68242714899934711
641 70645876521048756
642 73131764110703420
643 75703161587949692
644 78362944463412364
645 81114082785588233
646 83959644179656364
647 86902796982011992
648 89946813473213644
649 93095073212248372
650 96351066475602881
651 99718397804094961
652 103200789660647106
653 106802086202790604
654 110526257173144236
655 114377401911351095
656 118359753491589647
657 122477682989219198
658 126735703880372276
659 131138476578967314
660 135690813115046105
661 140397681958608369
662 145264212993805080
663 150295702647770794
664 155497619178660404
665 160875608128173479
666 166435497943257615
667 172183305771984384
668 178125243439339512
669 184267723608067954
670 190617366130033433
671 197181004594333925
672 203965693077803193
673 210978713103865972
674 218227580816532566
675 225720054375695847
676 233464141580253147
677 241468107726430189
678 249740483708051194
679 258290074365882794
680 267125967094071321
681 276257540711052293
682 285694474602718409
683 295446758146564368
684 305524700424879612
685 315938940235492071
686 326700456409542139
687 337820578445111831
688 349310997465992966
689 361183777515901444
690 373451367197783179
691 386126611668346821
692 399222764999029993
693 412753502913938368
694 426732935915820302
695 441175622812261005
696 456096584653610043
697 471511319094714249
698 487435815193702240
699 503886568660396274
700 520880597567521039
701 538435458539111587
702 556569263429851671
703 575300696509706400
704 594649032169508686
705 614634153162487459
706 635276569397402585
707 656597437300311529
708 678618579761323614
709 701362506683422898
710 724852436151867631
711 749112316242011995
712 774166847484170775
713 800041506005646434
714 826762567369385688
715 854357131129559868
716 882853146125940773
717 912279436538302103
718 942665728722960798
719 974042678855234258
720 1006441901400960004
721 1039895998441172263
722 1074438589875779433
723 1110104344531472994
724 1146929012200115668
725 1184949456635697962
726 1224203689537360857
727 1264730905547072385
728 1306571518292485506
729 1349767197504940474
730 1394360907243741390
731 1440396945259883571
732 1487920983531873945
733 1536980110007536274
734 1587622871587855310
735 1639899318388412210
736 1693861049315305553
737 1749561258994735490
738 1807054786094965220
739 1866398163080816816
740 1927649667443268404
741 1990869374446303643
742 2056119211434713406
743 2123463013749095964
744 2192966582293940584
745 2264697742806340722
746 2338726406875578217
747 2415124634763517816
748 2493966700077534884
749 2575329156350554046
750 2659290905582539662
751 2745933268799697343
752 2835340058690668742
753 2927597654378839676
754 3022795078391946004
755 3121024075893362736
756 3222379196239386177
757 3326957876929038668
758 3434860530016317828
759 3546190631054833994
760 3661054810647165136
761 3779562948674858431
762 3901828271285135850
763 4027967450712926226
764 4158100708020669686
765 4292351918838584624
766 4430848722190849221
767 4573722632497210134
768 4721109154839904784
769 4873147903588759292
770 5029982724481636102
771 5191761820257926471
772 5358637879945986434
773 5530768211909997194
774 5708314880762416196
775 5891444848251631866
776 6080330118239310929
777 6275147885882790526
778 6476080691141578102
779 6683316576732213732
780 6897049250656806674
781 7117478253434557359
782 7344809130171103433
783 7579253607601800364
784 7821029776249358884
785 8070362277842147086
786 8327482498140976529
787 8592628765326837623
788 8866046554108320754
789 9147988695709235304
790 9438715593901943026
791 9738495447258610843
792 10047604477794650891
793 10366327166184007814
794 10694956493733091224
795 11033794191302526244
796 11383150995371709545
797 11743346911448775925
798 12114711485031298298
799 12497584080329315776
800 12892314166970414812
801 13299261614909685021
802 13718796997774133849
803 14151301904879826312
804 14597169262163528256
805 15056803662277920839
806 15530621704108733179
807 16019052341976103039
808 16522537244790334072
809 17041531165442140998
810 17576502320711925771
811 18127932781991105541
812 18696318877119124251
813 19282171603644766088
814 19886017053829536274
815 20508396851722222461
816 21149868602639323967
817 21811006355395902067
818 22492401077643546300
819 23194661144678366734
820 23918412842092561181
821 24664300882656106273
822 25432988937822030413
823 26225160184260201722
824 27041517865838487984
825 27882785871477807561
826 28749709329319971487
827 29643055217662131635
828 30563612993120131846
829 31512195236496419300
830 32489638316844151159
831 33496803074228509293
832 34534575521700649549
833 35603867567016834376
834 36705617754645650780
835 37840792028621762223
836 39010384516823001687
837 40215418337259022093
838 41456946426976490510
839 42736052394205503332
840 44053851394384451147
841 45411491030718657673
842 46810152279949237355
843 48251050444022409140
844 49735436128369031324
845 51264596247526777269
846 52839855058852516855
847 54462575225093535881
848 56134158906610534162
849 57856048884061955940
850 59629729712381931083
851 61456728906910199305
852 63338618162550589318
853 65277014606859139374
854 67273582087990962132
855 69330032498454872983
856 71448127135651250935
857 73629678100198682746
858 75876549733076718792
859 78190660092640607832
860 80573982472596178923
861 83028546962046837821
862 85556442048755432326
863 88159816266798432728
864 90840879889815862696
865 93601906671093624149
866 96445235631752129951
867 99373272898343513912
868 102388493591195507592
869 105493443764880121502
870 108690742402216180907
871 111983083463253407841
872 115373237990728774978
873 118864056273519537272
874 122458470069659032610
875 126159494890527586507
876 129970232347867535848
877 133893872565316348622
878 137933696656201516872
879 142093079269380826108
880 146375491204960093719
881 150784502101773896356
882 155323783198558236096
883 159997110170796388602
884 164808366045276617778
885 169761544194447653673
886 174860751412714230488
887 180110211076876737664
888 185514266392970339048
889 191077383731819742158
890 196804156055692196311
891 202699306438487024936
892 208767691681965589448
893 215014306030596976042
894 221444284987655203890
895 228062909235274475763
896 234875608661245770456
897 241887966495403741482
898 249105723558529138302
899 256534782626774541772
900 264181212914692435407
901 272051254680026848944
902 280151323953518620228
903 288488017397051559908
904 297068117293555444724
905 305898596672177278833
906 314986624572315992948
907 324339571450211309148
908 333965014731880229404
909 343870744516285344050
910 354064769432722159005
911 364555322656523144024
912 375350868087274497380
913 386460106693852644324
914 397891983030706357312
915 409655691929916823513
916 421760685373687650532
917 434216679552044668764
918 447033662110640613020
919 460221899593688740800
920 473791945087186987047
921 487754646067718962512
922 502121152462257094486
923 516902924924541163098
924 532111743333740420160
925 547759715521257248522
926 563859286231689483688
927 580423246324114471082
928 597464742220019310180
929 614997285604372961440
930 633034763386493714422
931 651591447927539394392
932 670682007541631877876
933 690321517277798105554
934 710525469990097117084
935 731309787703500770528
936 752690833283280222092
937 774685422415852055308
938 797310835909251087918
939 820584832321596163468
940 844525660926132621824
941 869152075021664424104
942 894483345597404194036
943 920539275361503584914
944 947340213142773026420
945 974907068675332427328
946 1003261327776186599256
947 1032425067925984477964
948 1062420974263472303918
949 1093272356004422526930
950 1125003163296105577105
951 1157638004518642727944
952 1191202164044870757656
953 1225721620470656071890
954 1261223065327888568646
955 1297733922292700456945
956 1335282366901785410040
957 1373897346790009225264
958 1413608602462842244312
959 1454446688617498914908
960 1496442996027010604429
961 1539629774001822840584
962 1584040153443890105040
963 1629708170508608878452
964 1676668790890322644132
965 1724957934747543337587
966 1774612502284430196380
967 1825670400005490015250
968 1878170567660904582676
969 1932153005900318635292
970 1987658804653377012133
971 2044730172255774781476
972 2103410465340045117678
973 2163744219510799774206
974 2225777180824647903992
975 2289556338095515953043
976 2355129956046618760114
977 2422547609330881381394
978 2491860217442146826192
979 2563120080540072436178
980 2636380916212208371309
981 2711697897197328956238
982 2789127690094698322990
983 2868728495084586944718
984 2950560086685977710126
985 3034683855578057222547
986 3121162851512770913462
987 3210061827346390738384
988 3301447284218751074098
989 3395387517909542642794
990 3491952666401776197855
991 3591214758683288099658
992 3693247764817949219020
993 3798127647319016130152
994 3905932413857881481640
995 4016742171342328928033
996 4130639181399235320022
997 4247707917297542581154
998 4368035122348233769112
999 4491709869818949400186
1000 4618823624401826233473