0 1
1 1
2 2
3 3
4 3
5 5
6 7
7 9
8 12
9 16
10 20
11 26
12 33
13 41
14 51
15 64
16 79
17 97
18 119
19 144
20 175
21 212
22 254
23 305
24 365
25 434
26 516
27 612
28 722
29 851
30 1002
31 1174
32 1375
33 1607
34 1872
35 2179
36 2531
37 2933
38 3395
39 3923
40 4524
41 5211
42 5994
43 6881
44 7891
45 9038
46 10334
47 11804
48 13467
49 15341
50 17460
51 19849
52 22535
53 25561
54 28963
55 32780
56 37067
57 41874
58 47254
59 53280
60 60021
61 67549
62 75960
63 85347
64 95808
65 107470
66 120456
67 134899
68 150965
69 168819
70 188640
71 210643
72 235049
73 262093
74 292058
75 325236
76 361937
77 402531
78 447398
79 496950
80 551666
81 612043
82 678621
83 752019
84 832886
85 921927
86 1019940
87 1127769
88 1246327
89 1376643
90 1519811
91 1677009
92 1849561
93 2038875
94 2246470
95 2474045
96 2723406
97 2996506
98 3295514
99 3622743
100 3980696
101 4372136
102 4800017
103 5267532
104 5778195
105 6335769
106 6944314
107 7608289
108 8332468
109 9122006
110 9982546
111 10920131
112 11941286
113 13053130
114 14263299
115 15580029
116 17012284
117 18569686
118 20262601
119 22102297
120 24100866
121 26271327
122 28627810
123 31185473
124 33960634
125 36970974
126 40235454
127 43774479
128 47610122
129 51766054
130 56267738
131 61142672
132 66420349
133 72132468
134 78313225
135 84999292
136 92230050
137 100047946
138 108498477
139 117630483
140 127496551
141 138153022
142 149660350
143 162083557
144 175492291
145 189961241
146 205570665
147 222406502
148 240560857
149 260132628
150 281227669
151 303959366
152 328449375
153 354827852
154 383234150
155 413817671
156 446738189
157 482166683
158 520286328
159 561292943
160 605395974
161 652819647
162 703803577
163 758603918
164 817494735
165 880768781
166 948738853
167 1021739430
168 1100127635
169 1184284873
170 1274618750
171 1371564274
172 1475585827
173 1587179403
174 1706874132
175 1835234616
176 1972863554
177 2120403659
178 2278540411
179 2448005174
180 2629577554
181 2824088655
182 3032424779
183 3255530297
184 3494411542
185 3750141159
186 4023861609
187 4316789804
188 4630222227
189 4965539215
190 5324210441
191 5707800962
192 6117976415
193 6556509507
194 7025287177
195 7526316855
196 8061734151
197 8633811324
198 9244964804
199 9897764321
200 10594942888
201 11339405825
202 12134241597
203 12982733555
204 13888370789
205 14854860934
206 15886143996
207 16986405374
208 18160090955
209 19411923455
210 20746917941
211 22170399649
212 23688023277
213 25305791438
214 27030075733
215 28867639455
216 30825659525
217 32911751380
218 35133995671
219 37500964345
220 40021749965
221 42705997113
222 45563933339
223 48606403677
224 51844907596
225 55291635633
226 58959510013
227 62862228094
228 67014305666
229 71431124757
230 76128984644
231 81125152976
232 86437921991
233 92086668369
234 98091913567
235 104475389827
236 111260110380
237 118470440563
238 126132175253
239 134272621217
240 142920680787
241 152106942656
242 161863778409
243 172225440846
244 183228170449
245 194910308376
246 207312411920
247 220477379252
248 234450581576
249 249279998665
250 265016364815
251 281713323369
252 299427585639
253 318219101550
254 338151240273
255 359290976318
256 381709088944
257 405480373159
258 430683857430
259 457403036607
260 485726118168
261 515746276729
262 547561925916
263 581277005549
264 617001278978
265 654850650150
266 694947498333
267 737421025204
268 782407624360
269 830051271265
270 880503928037
271 933925973798
272 990486658681
273 1050364575505
274 1113748160746
275 1180836222705
276 1251838490749
277 1326976198101
278 1406482695866
279 1490604092237
280 1579599929904
281 1673743899525
282 1773324583062
283 1878646240661
284 1990029639261
285 2107812916295
286 2232352493227
287 2364024037251
288 2503223464152
289 2650367998321
290 2805897288140
291 2970274569688
292 3143987895944
293 3327551429625
294 3521506792733
295 3726424490982
296 3942905411473
297 4171582386738
298 4413121844374
299 4668225541093
300 4937632374096
301 5222120290419
302 5522508293487
303 5839658539596
304 6174478546651
305 6527923514622
306 6900998750537
307 7294762222078
308 7710327239483
309 8148865258925
310 8611608833020
311 9099854708755
312 9614967066363
313 10158380926457
314 10731605726660
315 11336229061286
316 11973920613629
317 12646436282964
318 13355622499932
319 14103420762562
320 14891872395561
321 15723123527295
322 16599430319308
323 17523164451798
324 18496818860535
325 19523013762473
326 20604502974929
327 21744180524750
328 22945087587492
329 24210419763280
330 25543534686539
331 26947960013089
332 28427401793109
333 29985753228159
334 31627103859762
335 33355749199781
336 35176200802380
337 37093196829368
338 39111713121105
339 41236974774916
340 43474468287134
341 45829954273584
342 48309480772904
343 50919397193447
344 53666368921978
345 56557392600899
346 59599812140331
347 62801335486992
348 66170052159280
349 69714451621433
350 73443442522366
351 77366372812366
352 81493050817424
353 85833767301102
354 90399318531715
355 95201030441749
356 100250783914956
357 105561041223823
358 111144873712438
359 117015990766698
360 123188770099725
361 129678289457133
362 136500359791131
363 143671559937445
364 151209272910618
365 159131723874156
366 167458019827193
367 176208191135029
368 185403234968645
369 195065160703957
370 205217037420742
371 215883043576774
372 227088518918086
373 238860018779307
374 251225370861818
375 264213734561658
376 277855663017363
377 292183167979151
378 307229787583869
379 323030657224470
380 339622583630262
381 357044122257243
382 375335658197865
383 394539490743164
384 414699921714076
385 435863347793475
386 458078357011616
387 481395829521366
388 505869042919586
389 531553782290141
390 558508455126403
391 586794211418260
392 616475069104385
393 647618045072294
394 680293292023499
395 714574241432445
396 750537752810625
397 788264269628798
398 827837982157871
399 869346997472769
400 912883517011504
401 958544021986809
402 1006429466931559
403 1056645481814329
404 1109302583064366
405 1164516393828300
406 1222407873945155
407 1283103560025957
408 1346735816006778
409 1413443094718544
410 1483370210912088
411 1556668626160846
412 1633496746247762
413 1714020231533690
414 1798412320790894
415 1886854169178056
416 1979535200921418
417 2076653477254407
418 2178416080370379
419 2285039514029630
420 2396750121449659
421 2513784521321999
422 2636390062682590
423 2764825299351151
424 2899360484882836
425 3040278088854829
426 3187873335301969
427 3342454764356180
428 3504344818020243
429 3673880451001681
430 3851413767785502
431 4037312686998902
432 4231961634118925
433 4435762263841011
434 4649134213299753
435 4872515887333090
436 5106365277264877
437 5351160814552005
438 5607402260645459
439 5875611634716504
440 6156334180767433
441 6450139375655290
442 6757621979876709
443 7079403132828153
444 7416131494271880
445 7768484434075354
446 8137169272158469
447 8522924570605476
448 8926521480255200
449 9348765143951906
450 9790496158667066
451 10252592099082251
452 10735969105093458
453 11241583535731653
454 11770433692400459
455 12323561614201780
456 12902054948165218
457 13507048897629405
458 14139728251894402
459 14801329500322351
460 15493143034521667
461 16216515442126267
462 16972851895751687
463 17763618641196949
464 18590345588844203
465 19454629012290720
466 20358134358768699
467 21302599175797979
468 22289836158614245
469 23321736323473006
470 24400272311825979
471 25527501830483206
472 26705571233469997
473 27936719251193424
474 29223280872671811
475 30567691387216087
476 31972490591871242
477 33440327171087891
478 34973963255772966
479 36576279168804999
480 38250278364285061
481 39999092568523778
482 41825987130719091
483 43734366591492672
484 45727780478238007
485 47809929336205730
486 49984671004499667
487 52256027147000262
488 54628190048227142
489 57105529684440327
490 59692601081183333
491 62394151968496539
492 65215130745358902
493 68160694765886741
494 71236218959879194
495 74447304800673849
496 77799789634323536
497 81299756384204323
498 84953543645589379
499 88767756185855679
500 92749275866130659
501 96905273000671212
502 101243218171489615
503 105770894515929482
504 110496410505448539
505 115428213235183326
506 120575102244118024
507 125946243886307263
508 131551186275027445
509 137399874822045312
510 143502668394900806
511 149870356116645540
512 156514174832866326
513 163445827271622506
514 170677500923602041
515 178221887670270790
516 186092204188693907
517 194302213163526698
518 202866245337234634
519 211799222430625471
520 221116680967747648
521 230834797039880874
522 240970412044497327
523 251541059437212056
524 262564992535537558
525 274061213414550555
526 286049502936909838
527 298550451960596862
528 311585493769202163
529 325176937772122252
530 339348004523114274
531 354122862107288824
532 369526663949390560
533 385585588097469176
534 402326878037879685
535 419778885100567265
536 437971112515040939
537 456934261179499405
538 476700277208862044
539 497302401329127912
540 518775220187789349
541 541154719653621936
542 564478340181086379
543 588785034317155341
544 614115326432310746
545 640511374759640942
546 668017035828853339
547 696677931386319257
548 726541517894754628
549 757657158709371044
550 790076199032035558
551 823852043747807932
552 859040238251834652
553 895698552379727902
554 933887067557772932
555 973668267293336073
556 1015107131131490280
557 1058271232207516046
558 1103230838529430413
559 1150059018130889477
560 1198831748238921225
561 1249628028605964254
562 1302529999162480124
563 1357623062151045014
564 1414996008908428008
565 1474741151469612151
566 1536954459172945481
567 1601735700451852681
568 1669188590006713415
569 1739420941556406016
570 1812544826375966216
571 1888676737835794212
572 1967937762164466883
573 2050453755664950355
574 2136355528623884251
575 2225779036161041365
576 2318865576274684197
577 2415761995349395946
578 2516620901401297257
579 2621600885345153782
580 2730866750579813068
581 2844589751197750130
582 2962947839135172983
583 3086125920592262463
584 3214316122063582177
585 3347718066330556555
586 3486539158782356523
587 3630994884443234261
588 3781309116097530004
589 3937714433919472778
590 4100452457027970162
591 4269774187401232062
592 4445940366603575441
593 4629221845791353335
594 4819899969481229297
595 5018266973583283539
596 5224626398217730640
597 5439293515852102490
598 5662595775316963497
599 5894873262276401548
600 6136479176749594520
601 6387780328303122973
602 6649157649553956376
603 6921006728645293401
604 7203738361383188998
605 7497779123744457124
606 7803571965491029628
607 8121576825654324704
608 8452271270678284179
609 8796151156037128818
610 9153731312175139379
611 9525546255643708117
612 9912150926341272849
613 10314121451796189843
614 10732055939463674271
615 11166575298041590298
616 11618324088847838736
617 12087971408336626657
618 12576211802868190272
619 13083766216888394863
620 13611382975712997885
621 14159838804152671615
622 14729939882261015025
623 15322522939530379384
624 15938456388906090343
625 16578641502040496445
626 17244013627255557011
627 17935543451733347791
628 18654238309509909398
629 19401143536900331313
630 20177343877039041877
631 20983964935281063342
632 21822174687268181066
633 22693185041526032076
634 23598253458526239071
635 24538684628212220673
636 25515832208055974647
637 26531100623788223384
638 27585946935015794226
639 28681882768016069384
640 29820476318081110045
641 31003354423863258714
642 32232204716258028641
643 33508777844451323828
644 34834889781845751902
645 36212424214673663466
646 37643335016205123526
647 39129648809556134163
648 40673467622205082490
649 42276971635436249254
650 43942422032036686671
651 45672163945686228320
652 47468629515602583053
653 49334341050122369113
654 51271914303024309418
655 53284061866535467407
656 55373596685092925665
657 57543435694071797062
658 59796603587838851197
659 62136236721636480694
660 64565587151954673799
661 67088026820212188993
662 69707051884728906362
663 72426287206140203122
664 75249490991584399373
665 78180559603171995423
666 81223532536431859061
667 84382597574628062101
668 87662096125037364253
669 91066528743483130578
670 94600560853640191302
671 98269028667841983042
672 102076945316348401861
673 106029507192273737267
674 110132100519613505378
675 114390308152059541090
676 118809916610558107772
677 123396923367830133542
678 128157544388349047729
679 133098221932564004340
680 138225632634448041750
681 143546695861755530261
682 149068582368695171776
683 154798723251046761381
684 160744819214086023466
685 166914850164036297301
686 173317085134121028635
687 179960092556661559690
688 186852750893054974568
689 194004259633858518607
690 201424150681615519445
691 209122300129487386071
692 217108940449188262992
693 225394673102168989925
694 233990481588469973148
695 242907744948138831443
696 252158251730604590783
697 261754214447920756716
698 271708284528314530098
699 282033567787025753486
700 292743640431992037737
701 303852565622515004620
702 315374910599644315324
703 327325764407646507556
704 339720756226563032695
705 352576074336524519906
706 365908485735181836912
707 379735356430316603836
708 394074672430423393371
709 408945061456818822253
710 424365815401605948294
711 440356913556625541730
712 456939046639365029103
713 474133641642647281852
714 491962887535805419597
715 510449761845972777462
716 529618058149054458399
717 549492414500919687535
718 570098342840369145328
719 591462259396463093983
720 613611516133866430021
721 636574433270982770520
722 660380332906784955225
723 685059573793426767843
724 710643587292947561711
725 737164914557630550019
726 764657244974870559793
727 793155455918755663816
728 822695653851941137405
729 853315216822818357001
730 885052838404463468533
731 917948573123361887161
732 952043883427470589025
733 987381688244808980514
734 1024006413185430968000
735 1061964042441352281545
736 1101302172440796822993
737 1142070067314952914551
738 1184318716237322427806
739 1228100892697712008213
740 1273471215774924048515
741 1320486213474284443173
742 1369204388198304003797
743 1419686284420977803348
744 1471994558638511536916
745 1526194051671636169610
746 1582351863397097785911
747 1640537429988419691083
748 1700822603748638853018
749 1763281735620383797263
750 1827991760461418283745
751 1895032285176635465068
752 1964485679800414740924
753 2036437171626281663351
754 2110974942483951543234
755 2188190229267052712649
756 2268177427818150575895
757 2351034200281140698447
758 2436861586034609986542
759 2525764116323415791011
760 2617849932709516140608
761 2713230909466960951928
762 2812022780049961684683
763 2914345267767108765077
764 3020322220799061762562
765 3130081751701435944802
766 3243756381539164447480
767 3361483188803286258738
768 3483403963265937287087
769 3609665364934319722731
770 3740419088269550849882
771 3875822031841588908216
772 4016036473596916032614
773 4161230251921282662320
774 4311576952685628380478
775 4467256102469307172064
776 4628453368160915378086
777 4795360763143394239550
778 4968176860276672989465
779 5147107011897886600213
780 5332363577066192440910
781 5524166156286440365816
782 5722741833953373514474
783 5928325428765702279989
784 6141159752367320651344
785 6361495876481073544624
786 6589593408808887898573
787 6825720777980769407130
788 7070155527844090649865
789 7323184621393809407212
790 7585104754653779372594
791 7856222680829097984421
792 8136855545059534332529
793 8427331230114516522460
794 8727988713380880011266
795 9039178435505645275408
796 9361262681067528580283
797 9694615971662639836270
798 10039625471801948136442
799 10396691408030623862010
800 10766227501692241178975
801 11148661415774110707723
802 11544435216283735856439
803 11954005848620491547716
804 12377845629421178116729
805 12816442754373134266901
806 13270301822504043833346
807 13739944377473511963511
808 14225909466407947140771
809 14728754216837207871349
810 15249054432308930152784
811 15787405207274475932256
812 16344421561858974117749
813 16920739097147040996356
814 17517014671635500062819
815 18133927099524711603826
816 18772177871541050212075
817 19432491899004669710397
818 20115618281878908086523
819 20822331101560594056880
820 21553430239194159984728
821 22309742220316780552595
822 23092121086666830819976
823 23901449296013831724907
824 24738638650894662379358
825 25604631257168258756705
826 26500400513329330927813
827 27426952131550751712550
828 28385325191454294992432
829 29376593227640378222897
830 30401865352039325967911
831 31462287412179520843411
832 32559043186501694350626
833 33693355617883467205628
834 34866488086574183248803
835 36079745723777145297837
836 37334476767154489532868
837 38632073959569238714011
838 39973975992419609722126
839 41361668994962351481800
840 42796688071064872316936
841 44280618884870241115963
842 45815099296904748030673
843 47401821052204710800790
844 49042531522087676277856
845 50739035501243026929954
846 52493197061868388478187
847 54306941466631215808168
848 56182257142289443764132
849 58121197715861263599752
850 60125884115291997873529
851 62198506736625630850201
852 64341327679749951328767
853 66556683054847558573951
854 68846985361750104869241
855 71214725944460250986094
856 73662477523174977564343
857 76192896806215062138249
858 78808727184338857292886
859 81512801509994080275966
860 84308044964139085629227
861 87197478013345207778029
862 90184219459974326551557
863 93271489588310764237049
864 96462613409614145056067
865 99761024009150040329880
866 103170265998348026131323
867 106693999075332381770060
868 110336001697169168046293
869 114100174867274787403327
870 117990546041535541213265
871 122011273156795281766742
872 126166648785478954511191
873 130461104420233848256272
874 134899214892587845698400
875 139485702929744843410335
876 144225443853762010123429
877 149123470427481812457968
878 154184977851723711911229
879 159415328918376359582304
880 164820059324171133785854
881 170404883150061938788044
882 176175698511284557781877
883 182138593383321689096409
884 188299851609157055262577
885 194665959093363921972530
886 201243610188740169601615
887 208039714281373693504531
888 215061402580198648611996
889 222316035117285083550541
890 229811207965291805990703
891 237554760678705179148629
892 245554783965685168018271
893 253819627597544317139203
894 262357908563095762728649
895 271178519475323074718840
896 280290637238047681636054
897 289703731980499185990505
898 299427576267930260380181
899 309472254596661027738296
900 319848173182188226528640
901 330566070049252291748825
902 341637025433020759142793
903 353072472500819498965709
904 364884208404124475035988
905 377084405670816030588064
906 389685623947995524792133
907 402700822105970771720240
908 416143370714332206620618
909 430027064901366448830941
910 444366137608388258105741
911 459175273250915846524557
912 474469621798968565484315
913 490264813289130472773633
914 506576972781398270338893
915 523422735774218072901695
916 540819264091512784088345
917 558784262255910610773860
918 577335994362805953983737
919 596493301470316967887096
920 616275619520649588323500
921 636702997808836349821432
922 657796118015290258260632
923 679576313819099499288776
924 702065591109488428619539
925 725286648813384566134682
926 749262900357560360814605
927 774018495784362936282554
928 799578344540605360485840
929 825968138959769395250030
930 853214378458262843560125
931 881344394467085057546363
932 910386376120882116361292
933 940369396727019348417523
934 971323441037963832921794
935 1003279433350953522943055
936 1036269266459633454702936
937 1070325831483063767831481
938 1105483048598249247698816
939 1141775898703106636096855
940 1179240456037574713058113
941 1217913921791383460035550
942 1257834658727833353659988
943 1299042226853794736804161
944 1341577420167020644052635
945 1385482304512775365137421
946 1430800256582716198509913
947 1477576004089927701136526
948 1525855667154997290734882
949 1575686800939039152976804
950 1627118439560620525226044
951 1680201141334621654217557
952 1734987035372168976627282
953 1791529869581920883918834
954 1849885060114157969059529
955 1910109742290335906157471
956 1972262823061999684289307
957 2036405035044234051391635
958 2102598992170137797505166
959 2170909247014159588590268
960 2241402349833521791583273
961 2314146909378387270560455
962 2389213655522893228951395
963 2466675503770687261497514
964 2546607621690155119259746
965 2629087497336128110958992
966 2714195009716502108875084
967 2802012501363891157132087
968 2892624853074177615171266
969 2986119560875609269312378
970 3082586815293933381119855
971 3182119582980949233205389
972 3284813690775806164884955
973 3390767912270374952591024
974 3500084056952077812086356
975 3612867061999678198869072
976 3729225086809707680885980
977 3849269610333444700778317
978 3973115531306661095510988
979 4100881271456718661580417
980 4232688881774031219515618
981 4368664151937409760561623
982 4508936722985381365764966
983 4653640203328218188723948
984 4802912288198133275196604
985 4956894882637897534809608
986 5115734228131008450542994
987 5279581032979498679485874
988 5448590606538513921295527
989 5622922997419916143140712
990 5802743135780383216931907
991 5988220979812781797425821
992 6179531666562988862906184
993 6376855667197831731000007
994 6580378946853409310984264
995 6790293129196751071168860
996 7006795665837567892320305
997 7230090010730753631747939
998 7460385799714310261304639
999 7697899035331496320367086
1000 7942852277090241372349591