0 1
1 1
2 1
3 1
4 2
5 2
6 3
7 4
8 5
9 6
10 8
11 9
12 12
13 14
14 17
15 20
16 25
17 29
18 35
19 41
20 49
21 57
22 68
23 78
24 93
25 107
26 125
27 144
28 168
29 192
30 223
31 255
32 294
33 335
34 385
35 437
36 501
37 568
38 647
39 732
40 833
41 939
42 1065
43 1199
44 1355
45 1523
46 1717
47 1925
48 2166
49 2425
50 2720
51 3040
52 3405
53 3797
54 4244
55 4727
56 5272
57 5863
58 6528
59 7247
60 8057
61 8933
62 9912
63 10975
64 12162
65 13446
66 14878
67 16430
68 18152
69 20021
70 22092
71 24335
72 26819
73 29510
74 32478
75 35698
76 39246
77 43087
78 47315
79 51895
80 56923
81 62370
82 68343
83 74806
84 81889
85 89552
86 97929
87 106996
88 116899
89 127604
90 139287
91 151915
92 165673
93 180542
94 196727
95 214204
96 233215
97 253737
98 276026
99 300085
100 326197
101 354357
102 384898
103 417826
104 453497
105 491945
106 533564
107 578393
108 626890
109 679107
110 735539
111 796283
112 861889
113 932460
114 1008633
115 1090544
116 1178881
117 1273839
118 1376183
119 1486137
120 1604580
121 1731778
122 1868692
123 2015678
124 2173805
125 2343473
126 2525904
127 2721578
128 2931833
129 3157269
130 3399377
131 3658841
132 3937360
133 4235730
134 4555821
135 4898608
136 5266173
137 5659619
138 6081309
139 6532529
140 7015885
141 7532903
142 8086491
143 8678385
144 9311875
145 9988954
146 10713259
147 11487140
148 12314650
149 13198445
150 14143101
151 15151662
152 16229196
153 17379234
154 18607429
155 19917779
156 21316645
157 22808578
158 24400630
159 26098054
160 27908711
161 29838518
162 31896309
163 34088806
164 36425812
165 38915013
166 41567333
167 44391437
168 47399572
169 50601532
170 54010914
171 57638873
172 61500555
173 65608490
174 69979635
175 74628130
176 79572796
177 84829651
178 90419649
179 96360772
180 102676439
181 109386863
182 116518046
183 124092817
184 132140103
185 140685466
186 149761187
187 159395962
188 169625615
189 180482430
190 192006235
191 204233138
192 217207527
193 230969820
194 245569265
195 261051230
196 277470416
197 294877465
198 313333260
199 332894409
200 353628419
201 375598641
202 398880008
203 423543151
204 449671366
205 477343432
206 506651654
207 537684036
208 570542939
209 605326312
210 642147809
211 681116521
212 722358311
213 765994768
214 812165355
215 861005242
216 912669091
217 967307190
218 1025090691
219 1086186834
220 1150785092
221 1219071097
222 1291254754
223 1367542186
224 1448165500
225 1533353651
226 1623363363
227 1718448496
228 1818893141
229 1924978759
230 2037019249
231 2155326805
232 2280248312
233 2412129453
234 2551353710
235 2698303890
236 2853403358
237 3017076087
238 3189789519
239 3372012603
240 3564261570
241 3767055044
242 3980962498
243 4206557604
244 4444468569
245 4695329161
246 4959832483
247 5238678673
248 5532631679
249 5842464945
250 6169020486
251 6513151886
252 6875787270
253 7257868501
254 7660417750
255 8084474322
256 8531163858
257 9001632116
258 9497118716
259 10018886621
260 10568299938
261 11146750676
262 11755739779
263 12396800342
264 13071583810
265 13781778316
266 14529199686
267 15315706641
268 16143295475
269 17014011266
270 17930048574
271 18893657129
272 19907248010
273 20973295711
274 22094448790
275 23273427348
276 24513140506
277 25816577685
278 27186932510
279 28627489959
280 30141755384
281 31733336474
282 33406080279
283 35163948137
284 37011160046
285 38952064880
286 40991290907
287 43133610137
288 45384097880
289 47747989252
290 50230847350
291 52838414375
292 55576786929
293 58452260493
294 61471515306
295 64641452004
296 67969387345
297 71462883813
298 75129953790
299 78978881710
300 83018440243
301 87257702603
302 91706270312
303 96374078634
304 101271634148
305 106409811819
306 111800106581
307 117454419444
308 123385322283
309 129605836303
310 136129708469
311 142971180618
312 150145281903
313 157667585715
314 165554517649
315 173823103836
316 182491292394
317 191577691435
318 201101909114
319 211084278166
320 221546213752
321 232509928492
322 243998806354
323 256037106183
324 268650356930
325 281865046350
326 295709037077
327 310211244847
328 325402073140
329 341313078842
330 357977431713
331 375429563770
332 393705652807
333 412843260273
334 432881836856
335 453862346570
336 475827800859
337 498822865018
338 522894420414
339 548091158434
340 574464168347
341 602066516353
342 630953866749
343 661184041750
344 692817675207
345 725917759009
346 760550327187
347 796783986303
348 834690637882
349 874344988240
350 915825309050
351 959212932868
352 1004593049228
353 1052054183134
354 1101689035975
355 1153593942058
356 1207869753760
357 1264621283164
358 1323958229221
359 1385994601545
360 1450849699400
361 1518647512423
362 1589517751631
363 1663595234700
364 1741020966255
365 1821941504755
366 1906510103462
367 1994886053393
368 2087235884757
369 2183732694539
370 2284557406313
371 2389898079238
372 2499951238424
373 2614921159515
374 2735021270305
375 2860473420316
376 2991509351043
377 3128369947461
378 3271306790977
379 3420581386681
380 3576466799534
381 3739246867871
382 3909217921104
383 4086687976214
384 4271978552039
385 4465423842468
386 4667372628934
387 4878187442020
388 5098246569988
389 5327943205727
390 5567687568902
391 5817906031607
392 6079043355830
393 6351561810926
394 6635943525370
395 6932689593065
396 7242322558242
397 7565385504122
398 7902444674110
399 8254088557406
400 8620930645357
401 9003608511382
402 9402786724575
403 9819155917245
404 10253435859211
405 10706374529580
406 11178751352088
407 11671376268922
408 12185093161001
409 12720778917500
410 13279347046645
411 13861746759491
412 14468966771941
413 15102034401270
414 15762019587247
415 16450033995339
416 17167235263194
417 17914826131857
418 18694058920439
419 19506234684650
420 20352707950277
421 21234885893680
422 22154233343384
423 23112272006548
424 24110585742320
425 25150819835063
426 26234686575135
427 27363964574454
428 28540504665399
429 29766229286390
430 31043138705817
431 32373310479811
432 33758906040882
433 35202170224914
434 36705438239285
435 38271135290732
436 39901783941540
437 41600003843005
438 43368519525932
439 45210160238500
440 47127868188592
441 49124698522639
442 51203828033146
443 53368555285767
444 55622309843819
445 57968652545205
446 60411285267093
447 62954051395012
448 65600946144147
449 68356117231754
450 71223875815871
451 74208697375775
452 77315233295900
453 80548312003598
454 83912951221455
455 87414359377983
456 91057948596927
457 94849336390445
458 98794359421240
459 102899075535484
460 107169778326530
461 111612999529214
462 116235524465990
463 121044394817484
464 126046924994054
465 131250705349963
466 136663619518727
467 142293848099875
468 148149887050123
469 154240551865135
470 160574997081324
471 167162721031353
472 174013586504025
473 181137826111786
474 188546064217310
475 196249322944433
476 204259045437196
477 212587102607501
478 221245817788085
479 230247974266432
480 239606841456661
481 249336183262824
482 259450285852588
483 269963966959637
484 280892605334600
485 292252151050689
486 304059156779582
487 316330789157784
488 329084861987131
489 342339848792245
490 356114918041857
491 370429946978654
492 385305559032880
493 400763139000160
494 416824872771428
495 433513764013277
496 450853676331711
497 468869351558546
498 487586454552085
499 507031593187160
500 527232365942486
501 548217383778397
502 570016320658758
503 592659937446052
504 616180135594892
505 640609983189975
506 665983771996000
507 692337045857775
508 719706661286594
509 748130818385250
510 777649125252740
511 808302631593021
512 840133897161348
513 873187028318702
514 907507750743723
515 943143449135235
516 980143244520389
517 1018558037306342
518 1058440589458533
519 1099845571214248
520 1142829648403590
521 1187451533076404
522 1233772076359949
523 1281854323250506
524 1331763611338380
525 1383567630138918
526 1437336526020945
527 1493142966388038
528 1551062251274639
529 1611172382691521
530 1673554183293805
531 1738291371338785
532 1805470686834136
533 1875181972491493
534 1947518307908646
535 2022576096908274
536 2100455210241460
537 2181259079849539
538 2265094850589371
539 2352073481889181
540 2442309909150985
541 2535923153282306
542 2633036492369511
543 2733777579729661
544 2838278626461089
545 2946676528593472
546 3059113061298019
547 3175735015729495
548 3296694405611357
549 3422148614543275
550 3552260615701340
551 3687199130317571
552 3827138861423919
553 3972260664233516
554 4122751794796820
555 4278806093212391
556 4440624248089908
557 4608413993453964
558 4782390390123419
559 4962776037201979
560 5149801371419728
561 5343704894324345
562 5544733490672969
563 5753142672375331
564 5969196917255187
565 6193169930838670
566 6425345006751036
567 6666015307686853
568 6915484248755128
569 7174065798910865
570 7442084888825830
571 7719877734114025
572 8007792269251343
573 8306188494199430
574 8615438935965431
575 8935929020177576
576 9268057562162856
577 9612237165097476
578 9968894742441514
579 10338471944589035
580 10721425714577315
581 11118228745120543
582 11529370069839205
583 11955355552648305
584 12396708516717255
585 12853970268522769
586 13327700766856180
587 13818479183821831
588 14326904616567677
589 14853596687620542
590 15399196302003750
591 15964366289679150
592 16549792210839662
593 17156183043216385
594 17784272038745037
595 18434817458633302
596 19108603484598650
597 19806441005018557
598 20529168584099941
599 21277653302442590
600 22052791787954727
601 22855511114330919
602 23686769897560008
603 24547559256298890
604 25438903978009390
605 26361863545246012
606 27317533375979894
607 28307045920027915
608 29331571978175265
609 30392321873517284
610 31490546854236215
611 32627540344695637
612 33804639437307575
613 35023226228477813
614 36284729405100275
615 37590625671066940
616 38942441434213231
617 40341754329218864
618 41790195011496849
619 43289448782625060
620 44841257497810351
621 46447421300691393
622 48109800651369963
623 49830318177588259
624 51610960831068760
625 53453781862453685
626 55360903113902132
627 57334517125976025
628 59376889574868760
629 61490361519650130
630 63677351993367184
631 65940360399524648
632 68281969266567061
633 70704846803383014
634 73211749827204116
635 75805526488226385
636 78489119381939474
637 81265568453522894
638 84138014305985677
639 87109701296036292
640 90183981050036430
641 93364315763445261
642 96654281937724246
643 100057573896135431
644 103578007755194292
645 107219525170799418
646 110986197558594179
647 114882230084920675
648 118911966151738594
649 123079891647716410
650 127390639713957258
651 131848995271914462
652 136459900087078780
653 141228457591062675
654 146159938261898020
655 151259784758617900
656 156533617637556102
657 161987240819341526
658 167626647661690494
659 173458026779551517
660 179487768496590876
661 185722471040409135
662 192168947395862580
663 198834231899101131
664 205725587517169848
665 212850512865646143
666 220216749940954379
667 227832291587796373
668 235705389711762579
669 243844563224866233
670 252258606767608530
671 260956599162194548
672 269947912675495042
673 279242222011219240
674 288849514146647825
675 298780097897487031
676 309044614363110005
677 319654047099378099
678 330619733209792203
679 341953374163590849
680 353667047571949145
681 365773218691506962
682 378284752926993344
683 391214928062243359
684 404577447533699209
685 418386453433393303
686 432656540599909850
687 447402770441112072
688 462640685891798905
689 478386326106275851
690 494656242335531473
691 511467513542630006
692 528837763254801621
693 546785176158476226
694 565328515984855148
695 584487143144217692
696 604281033707697866
697 624730798143925911
698 645857701462860171
699 667683683122293910
700 690231378403346887
701 713524139557768387
702 737586058489553130
703 762441989218046830
704 788117571943898446
705 814639256908186352
706 842034329925398921
707 870330937722892733
708 899558115029236390
709 929745811483156384
710 960924920370107310
711 993127307195935130
712 1026385840169832028
713 1060734420542868688
714 1096208014942095452
715 1132842687579841065
716 1170675634549129191
717 1209745218016735750
718 1250091002596390544
719 1291753791644479951
720 1334775665835189563
721 1379200021684554843
722 1425071612458196301
723 1472436589057702669
724 1521342543399049465
725 1571838551802355425
726 1623975220988075860
727 1677804734119243652
728 1733380899570261850
729 1790759199780422570
730 1849996842958955538
731 1911152814917036561
732 1974287933883241918
733 2039464905490814965
734 2106748380886921316
735 2176205015063258462
736 2247903528452925969
737 2321914768802500967
738 2398311776462631111
739 2477169850010995980
740 2558566615453709395
741 2642582095821826161
742 2729298784512982762
743 2818801719096047045
744 2911178559036774940
745 3006519663958558153
746 3104918176008950746
747 3206470102839954717
748 3311274404886818146
749 3419433083345486440
750 3531051272651889171
751 3646237333749952832
752 3765102952075085227
753 3887763236424270619
754 4014336822764658962
755 4144945979034094338
756 4279716715115359889
757 4418778893914104625
758 4562266347857689591
759 4710316996618684778
760 4863072970517516356
761 5020680735279653758
762 5183291222744277569
763 5351059963065222267
764 5524147223149630738
765 5702718146737547880
766 5886942901018431942
767 6076996825047900598
768 6273060585016876364
769 6475320331489854875
770 6683967863827216669
771 6899200796758444647
772 7121222734486258176
773 7350243447136123603
774 7586479055102390932
775 7830152215945903033
776 8081492319572708609
777 8340735686185595982
778 8608125772919097571
779 8883913383483740680
780 9168356886917918968
781 9461722439599512204
782 9764284216811112915
783 10076324647833480926
784 10398134661059565010
785 10730013932923167653
786 11072271147340375040
787 11425224259268983666
788 11789200769298264397
789 12164538002681306601
790 12551583399939881247
791 12950694812257722578
792 13362240809017737810
793 13786600990493836104
794 14224166313287626376
795 14675339421310936983
796 15140534990142967441
797 15620180077349676642
798 16114714486841461036
799 16624591139633845295
800 17150276459344459969
801 17692250764563284077
802 18251008676690952339
803 18827059535150389111
804 19420927828837577733
805 20033153635474843471
806 20664293078014313673
807 21314918789507757305
808 21985620395877171737
809 22677005007750880216
810 23389697731096552527
811 24124342187553549738
812 24881601054504864669
813 25662156615523024619
814 26466711331544540283
815 27295988423134569751
816 28150732474521987222
817 29031710049482198162
818 29939710330086344089
819 30875545768103760418
820 31840052760420920786
821 32834092337968256164
822 33858550879875000947
823 34914340842035503753
824 36002401512178079441
825 37123699780305319148
826 38279230936974741930
827 39470019487968749698
828 40697119998214046158
829 41961617953166266014
830 43264630650926500830
831 44607308112965146439
832 45990834027134023623
833 47416426710496069909
834 48885340106082537087
835 50398864800746674995
836 51958329078669446805
837 53565099997318379324
838 55220584500869371781
839 56926230557518408102
840 58683528336163372864
841 60494011408493695419
842 62359257992456527198
843 64280892222739809896
844 66260585464739179204
845 68300057657245019407
846 70401078700832450810
847 72565469876770449952
848 74795105313968503727
849 77091913488348249140
850 79457878772705019102
851 81895043021010807438
852 84405507205789367202
853 86991433092061991085
854 89655044967082072013
855 92398631408894776242
856 95224547113539533654
857 98135214763461867045
858 101133126957572958985
859 104220848185035551085
860 107401016863858858892
861 110676347425883402322
862 114049632469896407275
863 117523744963952852450
864 121101640519323910190
865 124786359716622898957
866 128581030507237359132
867 132488870670082011134
868 136513190347523405501
869 140657394639947134704
870 144924986283565947030
871 149319568390375445761
872 153844847275631443673
873 158504635351180546285
874 163302854110810933250
875 168243537185370744808
876 173330833494641740527
877 178569010473110120167
878 183962457397473710840
879 189515688792410340532
880 195233347943317377898
881 201120210491920755657
882 207181188144364740287
883 213421332467031696185
884 219845838800638181221
885 226460050267195516531
886 233269461901337771761
887 240279724879934294040
888 247496650882479840254
889 254926216555484792748
890 262574568114385653068
891 270448026055491014399
892 278553090012534475247
893 286896443729632200904
894 295484960186304696748
895 304325706845618157308
896 313425951062233664639
897 322793165620664232785
898 332435034441683689150
899 342359458426421426989
900 352574561477283266770
901 363088696664440607684
902 373910452578268917528
903 385048659835672365373
904 396512397781946734070
905 408311001355301287488
906 420454068157007419655
907 432951465693451589974
908 445813338834425020250
909 459050117453070724529
910 472672524293218903838
911 486691583028663371866
912 501118626561557762855
913 515965305523588301492
914 531243597028603423911
915 546965813639447075883
916 563144612599215529367
917 579793005288763704957
918 596924366962274578942
919 614552446721767837505
920 632691377784014328798
921 651355687999768590143
922 670560310680481579723
923 690320595691431174906
924 710652320868187970550
925 731571703714349521135
926 753095413439281183173
927 775240583292778236589
928 798024823257255848716
929 821466233053352720178
930 845583415521489445283
931 870395490334208138965
932 895922108103840754064
933 922183464839259708736
934 949200316818318232188
935 976993995828651239520
936 1005586424845577179170
937 1035000134098658070041
938 1065258277597870538165
939 1096384650069818325695
940 1128403704377211603586
941 1161340569370907932626
942 1195221068250093551037
943 1230071737378733121902
944 1265919845636307613832
945 1302793414249789599067
946 1340721237187384144448
947 1379732902059798004843
948 1419858811612163325998
949 1461130205751161158714
950 1503579184193165900744
951 1547238729676727619880
952 1592142731827984126128
953 1638326011621085459563
954 1685824346525092658272
955 1734674496278168768055
956 1784914229383501181719
957 1836582350266499531032
958 1889718727190770619831
959 1944364320871137048280
960 2000561213884373565420
961 2058352640814620930434
962 2117783019237442638163
963 2178897981478170614354
964 2241744407251892329255
965 2306370457119410868214
966 2372825606870039820057
967 2441160682764222141250
968 2511427897750475979235
969 2583680888588310598220
970 2657974753995364189331
971 2734366093749063238486
972 2812913048864940059069
973 2893675342780539286152
974 2976714323671080952030
975 3062093007824442148822
976 3149876124205777073084
977 3240130160137975784204
978 3332923408232584988683
979 3428326014496007118928
980 3526410027750066989095
981 3627249450290383255610
982 3730920289926236302082
983 3837500613324003169940
984 3947070600802622112259
985 4059712602501772667541
986 4175511196076185448951
987 4294553245835393658069
988 4416927963487445717532
989 4542726970404536404661
990 4672044361574369059620
991 4804976771153838689703
992 4941623439794342903510
993 5082086283653961176429
994 5226469965271476766125
995 5374881966216159672905
996 5527432661694162165073
997 5684235397024117119000
998 5845406566168892068611
999 6011065692234788016460
1000 6181335510131432340019