0 1
1 1
2 1
3 2
4 2
5 3
6 4
7 4
8 5
9 7
10 8
11 10
12 12
13 14
14 18
15 22
16 25
17 30
18 36
19 42
20 50
21 58
22 67
23 79
24 92
25 106
26 123
27 142
28 164
29 189
30 217
31 248
32 284
33 325
34 370
35 421
36 479
37 543
38 616
39 698
40 788
41 890
42 1005
43 1131
44 1273
45 1432
46 1606
47 1802
48 2020
49 2259
50 2527
51 2824
52 3150
53 3514
54 3916
55 4358
56 4849
57 5390
58 5984
59 6642
60 7366
61 8160
62 9036
63 9999
64 11054
65 12216
66 13490
67 14884
68 16416
69 18094
70 19928
71 21938
72 24136
73 26536
74 29162
75 32030
76 35156
77 38571
78 42296
79 46352
80 50776
81 55594
82 60834
83 66542
84 72751
85 79496
86 86832
87 94802
88 103452
89 112848
90 123044
91 134097
92 146089
93 159088
94 173166
95 188422
96 204940
97 222812
98 242159
99 263085
100 285705
101 310164
102 336594
103 365138
104 395972
105 429259
106 465175
107 503935
108 545742
109 590812
110 639406
111 691772
112 748179
113 808943
114 874369
115 944786
116 1020576
117 1102115
118 1189806
119 1284111
120 1385489
121 1494431
122 1611498
123 1737250
124 1872285
125 2017280
126 2172916
127 2339921
128 2519113
129 2711318
130 2917420
131 3138403
132 3375270
133 3629092
134 3901053
135 4192367
136 4504326
137 4838356
138 5195923
139 5578586
140 5988058
141 6426103
142 6894601
143 7395608
144 7931246
145 8503776
146 9115658
147 9769444
148 10467849
149 11213817
150 12010408
151 12860874
152 13768736
153 14737660
154 15771538
155 16874572
156 18051143
157 19305906
158 20643872
159 22070272
160 23590660
161 25211002
162 26937538
163 28776889
164 30736150
165 32822752
166 35044572
167 37410044
168 39928006
169 42607820
170 45459495
171 48493526
172 51721030
173 55153874
174 58804506
175 62686108
176 66812729
177 71199121
178 75860896
179 80814672
180 86077906
181 91669062
182 97607780
183 103914695
184 110611623
185 117721746
186 125269424
187 133280409
188 141782036
189 150803036
190 160373767
191 170526425
192 181294862
193 192714832
194 204824221
195 217662868
196 231272832
197 245698655
198 260987177
199 277187826
200 294352914
201 312537449
202 331799468
203 352200352
204 373804641
205 396680407
206 420899598
207 446537872
208 473674997
209 502395232
210 532787177
211 564944211
212 598964929
213 634952992
214 673017616
215 713274059
216 755843488
217 800853533
218 848438815
219 898740839
220 951908614
221 1008099236
222 1067477824
223 1130218196
224 1196503523
225 1266526305
226 1340489121
227 1418605372
228 1501099292
229 1588206784
230 1680176258
231 1777268689
232 1879758565
233 1987934815
234 2102100932
235 2222576034
236 2349695904
237 2483813200
238 2625298635
239 2774542141
240 2931953177
241 3097962044
242 3273021214
243 3457605728
244 3652214674
245 3857372687
246 4073630463
247 4301566442
248 4541788478
249 4794934498
250 5061674400
251 5342711928
252 5638785521
253 5950670427
254 6279180822
255 6625170860
256 6989537050
257 7373220664
258 7777209000
259 8202538061
260 8650295278
261 9121621034
262 9617711700
263 10139822694
264 10689270310
265 11267435146
266 11875765559
267 12515779858
268 13189070158
269 13897306284
270 14642238376
271 15425701230
272 16249618736
273 17116006927
274 18026978880
275 18984749746
276 19991640316
277 21050082584
278 22162625412
279 23331938704
280 24560819697
281 25852199360
282 27209147286
283 28634878778
284 30132762088
285 31706324110
286 33359258380
287 35095433290
288 36918898664
289 38833894802
290 40844861776
291 42956447032
292 45173515634
293 47501160756
294 49944712460
295 52509749276
296 55202110066
297 58027904162
298 60993524424
299 64105660664
300 67371311308
301 70797798147
302 74392781540
303 78164273782
304 82120655768
305 86270694194
306 90623556872
307 95188831582
308 99976545495
309 104997182702
310 110261705522
311 115781576444
312 121568778196
313 127635837784
314 133995851288
315 140662506791
316 147650111506
317 154973619830
318 162648659460
319 170691562028
320 179119394790
321 187949990376
322 197201981401
323 206894836216
324 217048892778
325 227685397712
326 238826546662
327 250495522842
328 262716541074
329 275514893331
330 288916992543
331 302950422262
332 317643988080
333 333027767328
334 349133165076
335 365992972142
336 383641421457
337 402114251227
338 421448770314
339 441683922120
340 462860355782
341 485020499864
342 508208634748
343 532470972813
344 557855741477
345 584413265147
346 612196055512
347 641258905136
348 671658980106
349 703455921706
350 736711951835
351 771491977713
352 807863706373
353 845897763304
354 885667810732
355 927250676472
356 970726487442
357 1016178803237
358 1063694761039
359 1113365225843
360 1165284941174
361 1219552692040
362 1276271473938
363 1335548662768
364 1397496198041
365 1462230772907
366 1529874025645
367 1600552745610
368 1674399086782
369 1751550783470
370 1832151381712
371 1916350479207
372 2004303968211
373 2096174295403
374 2192130731382
375 2292349644012
376 2397014790189
377 2506317618494
378 2620457576601
379 2739642438765
380 2864088645565
381 2994021649482
382 3129676282424
383 3271297136903
384 3419138954370
385 3573467037493
386 3734557677715
387 3902698591499
388 4078189382582
389 4261342021430
390 4452481335033
391 4651945525074
392 4860086705454
393 5077271451899
394 5303881382651
395 5540313760842
396 5786982111014
397 6044316869703
398 6312766060206
399 6592795983890
400 6884891948807
401 7189559025349
402 7507322821156
403 7838730296794
404 8184350611735
405 8544775992588
406 8920622645994
407 9312531705475
408 9721170203779
409 10147232094274
410 10591439310310
411 11054542853781
412 11537323937620
413 12040595170582
414 12565201775485
415 13112022866709
416 13681972774874
417 14276002409768
418 14895100688275
419 15540296015020
420 16212657806570
421 16913298087043
422 17643373142643
423 18404085225510
424 19196684336186
425 20022470071822
426 20882793530234
427 21779059300566
428 22712727527103
429 23685316036357
430 24698402559496
431 25753627036274
432 26852693990512
433 27997375010438
434 29189511319914
435 30431016430357
436 31723878908155
437 33070165243384
438 34472022809272
439 35931682949008
440 37451464175354
441 39033775472286
442 40681119737100
443 42396097347925
444 44181409845934
445 46039863772456
446 47974374645556
447 49987971065444
448 52083798990568
449 54265126168884
450 56535346713603
451 58897985867136
452 61356704937688
453 63915306397516
454 66577739188892
455 69348104221976
456 72230660053548
457 75229828795045
458 78350202233646
459 81596548155688
460 84973816923124
461 88487148286584
462 92141878424616
463 95943547262002
464 99897906050907
465 104010925204548
466 108288802438836
467 112737971205900
468 117365109409160
469 122177148458418
470 127181282648882
471 132384978854053
472 137795986594038
473 143422348463066
474 149272410906796
475 155354835414072
476 161678610107012
477 168253061720721
478 175087868040315
479 182193070779700
480 189579088893990
481 197256732396672
482 205237216666568
483 213532177236934
484 222153685141809
485 231114262805181
486 240426900466064
487 250105073218812
488 260162758654592
489 270614455098430
490 281475200525370
491 292760592142363
492 304486806631757
493 316670621144106
494 329329435028228
495 342481292295717
496 356144904912358
497 370339676905806
498 385085729287963
499 400403925890035
500 416315900100918
501 432844082509116
502 450011729551921
503 467842953163792
504 486362751426552
505 505597040330981
506 525572686643565
507 546317541883594
508 567860477526212
509 590231421427663
510 613461395480578
511 637582554621608
512 662628227190369
513 688632956650267
514 715632544801088
515 743664096485180
516 772766065801077
517 802978303962564
518 834342108807874
519 866900275977077
520 900697151904045
521 935778688631232
522 972192500469956
523 1009987922661197
524 1049216072049722
525 1089929909799012
526 1132184306311603
527 1176036108372691
528 1221544208549440
529 1268769617021514
530 1317775535865917
531 1368627435834514
532 1421393135811339
533 1476142884978317
534 1532949447734933
535 1591888191571050
536 1653037177928086
537 1716477256101877
538 1782292160399150
539 1850568610590709
540 1921396415722931
541 1994868581513591
542 2071081421383748
543 2150134671196148
544 2232131607941899
545 2317179172436410
546 2405388096105223
547 2496873032118349
548 2591752690944065
549 2690149980414606
550 2792192150580236
551 2898010943434062
552 3007742747612992
553 3121528758370233
554 3239515142914945
555 3361853211238431
556 3488699592743026
557 3620216418783936
558 3756571511258354
559 3897938577581194
560 4044497412173441
561 4196434104614355
562 4353941254821857
563 4517218195404048
564 4686471221352474
565 4861913827468046
566 5043766953681782
567 5232259238462167
568 5427627280728395
569 5630115910453623
570 5839978468172858
571 6057477093845978
572 6282883025284020
573 6516476906378122
574 6758549105616169
575 7009400045121269
576 7269340540479217
577 7538692151877222
578 7817787546816340
579 8106970874695948
580 8406598153832540
581 8717037671206883
582 9038670395272011
583 9371890402427319
584 9717105317488282
585 10074736768521388
586 10445220856696572
587 10829008641525680
588 11226566641896765
589 11638377353608373
590 12064939783814744
591 12506770002836346
592 12964401714096148
593 13438386842638596
594 13929296142735564
595 14437719825400205
596 14964268206316815
597 15509572374745512
598 16074284884287886
599 16659080466078764
600 17264656765022134
601 17891735100028846
602 18541061248883653
603 19213406258424049
604 19909567281067096
605 20630368438379698
606 21376661712446000
607 22149327866153290
608 22949277393165836
609 23777451498419259
610 24634823110348856
611 25522397925703048
612 26441215487860750
613 27392350299965666
614 28376912973819144
615 29396051415544264
616 30450952049443017
617 31542841081087112
618 32672985800757368
619 33842695928772786
620 35053325003857694
621 36306271815774360
622 37602981883891754
623 38944948982956343
624 40333716717416312
625 41770880146110288
626 43258087458715612
627 44797041705443086
628 46389502581941314
629 48037288270948126
630 49742277342323551
631 51506410713593480
632 53331693672697232
633 55220197964734078
634 57174063945019644
635 59195502800314940
636 61286798840199394
637 63450311861096307
638 65688479584998246
639 68003820175057538
640 70398934830764412
641 72876510464963076
642 75439322465082308
643 78090237541535518
644 80832216665763213
645 83668318100524698
646 86601700525647582
647 89635626261951000
648 92773464596200260
649 96018695210578428
650 99374911719655596
651 102845825317988112
652 106435268542134400
653 110147199150356666
654 113985704123441608
655 117955003790753716
656 122059456085106180
657 126303560930210708
658 130691964765174768
659 135229465209977150
660 139921015876040534
661 144771731326756408
662 149786892192270562
663 154971950443036890
664 160332534827417010
665 165874456478044816
666 171603714691888834
667 177526502889748930
668 183649214760353898
669 189978450594457796
670 196521023815170022
671 203283967710174530
672 210274542371742761
673 217500241851316650
674 224968801534851590
675 232688205745375382
676 240666695580129276
677 248912776989063360
678 257435229101742636
679 266243112810672599
680 275345779618450518
681 284752880756453850
682 294474376583773216
683 304520546274486286
684 314901997801699046
685 325629678227820756
686 336714884309921833
687 348169273429379722
688 360004874856103484
689 372234101357007840
690 384869761158788964
691 397925070276189914
692 411413665216321068
693 425349616070009501
694 439747440002342024
695 454622115153940700
696 469989094964949024
697 485864322934955278
698 502264247831450694
699 519205839359895508
700 536706604309772543
701 554784603190379606
702 573458467370625220
703 592747416738459616
704 612671277894949682
705 633250502898557804
706 654506188576618664
707 676460096420390657
708 699134673080650408
709 722553071482306364
710 746739172575895474
711 771717607744464898
712 797513781885924500
713 824153897190351384
714 851664977632417929
715 880074894200777091
716 909412390885646404
717 939707111446577404
718 970989626984142334
719 1003291464338695446
720 1036645135340168488
721 1071084166934695107
722 1106643132213304445
723 1143357682368787388
724 1181264579608772522
725 1220401731052515632
726 1260808223639837674
727 1302524360082683330
728 1345591695889263393
729 1390053077491751697
730 1435952681510651964
731 1483336055188471906
732 1532250158026430698
733 1582743404660184106
734 1634865709010112454
735 1688668529742890207
736 1744204917083437427
737 1801529561015957471
738 1860698840914029588
739 1921770876642241428
740 1984805581171496508
741 2049864714751496742
742 2117011940686558689
743 2186312882760623757
744 2257835184358799929
745 2331648569335579538
746 2407824904679640432
747 2486438265026734714
748 2567564999075134106
749 2651283797957935941
750 2737675765628256627
751 2826824491316475631
752 2918816124118607020
753 3013739449776734128
754 3111685969715765336
755 3212749982400768292
756 3317028667081147579
757 3424622169991450783
758 3535633693078681873
759 3650169585328172978
760 3768339436763793744
761 3890256175198479272
762 4016036165813406226
763 4145799313648096475
764 4279669169084052897
765 4417773036407067887
766 4560242085537534674
767 4707211467018552240
768 4858820430354351738
769 5015212445796022752
770 5176535329672124251
771 5342941373364722795
772 5514587476036128681
773 5691635281212367304
774 5874251317332623248
775 6062607142378916230
776 6256879492701214648
777 6457250436156652709
778 6663907529686852501
779 6877043981458501247
780 7096858817696071236
781 7323557054341245040
782 7557349873674977729
783 7798454806042163818
784 8047095916824919907
785 8303503998812101259
786 8567916770117032641
787 8840579077801869820
788 9121743107368876078
789 9411668598283616459
790 9710623065701926294
791 10018882028574667465
792 10336729244309387255
793 10664456950175295927
794 11002366111640456708
795 11350766677835593192
796 11709977844346703929
797 12080328323541500522
798 12462156622640638647
799 12855811329753019745
800 13261651408097645129
801 13680046498640937858
802 14111377231387316582
803 14556035545564420681
804 15014425018951343510
805 15486961206607697004
806 15974071989265398455
807 16476197931652591759
808 16993792651029222526
809 17527323196218352672
810 18077270437425425929
811 18644129467148495210
812 19228410012487530286
813 19830636859169701705
814 20451350287619085513
815 21091106521404925706
816 21750478188412076836
817 22430054795089600389
818 23130443214139817178
819 23852268186020372722
820 24596172834645081937
821 25362819197676344727
822 26152888771813006774
823 26967083073491671186
824 27806124215427254329
825 28670755499430551564
826 29561742025955705038
827 30479871320839080111
828 31425953979703988841
829 32400824330521900510
830 33405341114830287534
831 34440388188121226451
832 35506875239932229620
833 36605738534181261184
834 37737941670302989969
835 38904476365761924541
836 40106363260529610470
837 41344652744129384108
838 42620425805872098435
839 43934794908918924492
840 45288904888824952186
841 46683933877238669391
842 48121094251446334907
843 49601633610469289180
844 51126835778445150548
845 52698021836039129981
846 54316551180652250036
847 55983822616217821050
848 57701275473394273911
849 59470390760984652357
850 61292692349439419172
851 63169748187317565612
852 65103171551604995218
853 67094622332817423500
854 69145808355835097022
855 71258486737442530155
856 73434465281576797883
857 75675603913309852892
858 77983816152618292554
859 80361070629026574746
860 82809392638233628406
861 85330865741862991734
862 87927633411511584917
863 90601900718298353637
864 93355936069146617636
865 96192072991071510518
866 99112711964772393026
867 102120322308865317832
868 105217444116130948586
869 108406690243184399281
870 111690748355011451419
871 115072383025858920156
872 118554437898000778372
873 122139837899942651838
874 125831591525673836280
875 129632793176612818828
876 133546625567936544408
877 137576362201033672181
878 141725369903862133988
879 145997111441039080346
880 150395148195545028388
881 154923142923967595924
882 159584862587261765890
883 164384181259061361066
884 169325083113623771705
885 174411665495545613404
886 179648142073449046498
887 185038846079889945372
888 190588233639799131726
889 196300887189834594046
890 202181518991078488918
891 208234974737577483719
892 214466237263296713708
893 220880430350118268592
894 227482822639585000676
895 234278831651167540348
896 241274027909898201346
897 248474139186290842012
898 255885054851548630625
899 263512830351133031954
900 271363691799848642578
901 279444040701687618724
902 287760458797754821362
903 296319713045682496864
904 305128760734039144484
905 314194754735321083615
906 323525048901209809938
907 333127203603881286798
908 343008991427244170588
909 353178403012085967412
910 363643653059216940974
911 374413186494799992488
912 385495684802164722913
913 396900072524523063790
914 408635523943110414564
915 420711469935394811930
916 433137605018124827144
917 445923894580102225170
918 459080582309693264856
919 472618197822230375199
920 486547564492580746770
921 500879807498296198480
922 515626362078906951320
923 530798982017056948974
924 546409748347326935790
925 562471078298750970713
926 578995734477178071001
927 595996834293790818798
928 613487859646264274798
929 631482666859206430280
930 649995496890694013970
931 669040985811901942290
932 688634175566995378245
933 708790525020639344733
934 729525921300679259726
935 750856691443730210152
936 772799614351613186204
937 795371933066789919214
938 818591367375147251182
939 842476126744697902307
940 867044923608994047619
941 892316987004265386470
942 918312076569526039192
943 945050496919141486628
944 972553112397579270674
945 1000841362226317797970
946 1029937276053153121053
947 1059863489914394624381
948 1090643262620710502362
949 1122300492577669514158
950 1154859735052296517805
951 1188346219897250056526
952 1222785869744537437650
953 1258205318680975254755
954 1294631931417916471195
955 1332093822968095531688
956 1370619878842758623826
957 1410239775782583465115
958 1450984003036248259676
959 1492883884200850045904
960 1535971599638735806619
961 1580280209485691779429
962 1625843677265803798616
963 1672696894128692498938
964 1720875703725238093925
965 1770416927738305682340
966 1821358392085402991060
967 1873738953810644313671
968 1927598528683821681699
969 1982978119524837480808
970 2039919845272227850782
971 2098466970814966883931
972 2158663937607229450588
973 2220556395086301365822
974 2284191232914322225613
975 2349616614065071283477
976 2416882008777556060782
977 2486038229398698648290
978 2557137466137979716467
979 2630233323757490889582
980 2705380859221422958530
981 2782636620329625490739
982 2862058685360508420907
983 2943706703749177710128
984 3027641937827351498014
985 3113927305652285877389
986 3202627424952608980118
987 3293808658219666102844
988 3387539158973712528077
989 3483888919235011932013
990 3582929818230655710274
991 3684735672368707515106
992 3789382286512054080015
993 3896947506585158224132
994 4007511273547758021590
995 4121155678770392597811
996 4237965020847511487667
997 4358025863884836089900
998 4481427097298542384158
999 4608259997164776801811
1000 4738618289158996937374