0 1
1 1
2 1
3 2
4 3
5 3
6 5
7 7
8 8
9 11
10 15
11 17
12 23
13 30
14 35
15 44
16 57
17 66
18 82
19 103
20 121
21 146
22 181
23 211
24 253
25 308
26 360
27 425
28 513
29 596
30 700
31 834
32 969
33 1127
34 1333
35 1541
36 1786
37 2093
38 2415
39 2781
40 3241
41 3723
42 4273
43 4946
44 5669
45 6476
46 7461
47 8519
48 9705
49 11123
50 12669
51 14379
52 16418
53 18638
54 21101
55 23993
56 27173
57 30671
58 34763
59 39256
60 44211
61 49940
62 56267
63 63207
64 71204
65 80020
66 89707
67 100771
68 113011
69 126410
70 141666
71 158513
72 176980
73 197861
74 220963
75 246221
76 274703
77 306156
78 340573
79 379176
80 421843
81 468440
82 520578
83 578103
84 640961
85 710993
86 788274
87 872593
88 966342
89 1069617
90 1182326
91 1307212
92 1444755
93 1594677
94 1760495
95 1942825
96 2141575
97 2360787
98 2601702
99 2864038
100 3152926
101 3469935
102 3815091
103 4194311
104 4610164
105 5062517
106 5558821
107 6102305
108 6693353
109 7340584
110 8048796
111 8818335
112 9659985
113 10579732
114 11578794
115 12669702
116 13860868
117 15153731
118 16563889
119 18101789
120 19770330
121 21587707
122 23568077
123 25715074
124 28051260
125 30594123
126 33349716
127 36344483
128 39601526
129 43128541
130 46958212
131 51118970
132 55622463
133 60507165
134 65809926
135 71545599
136 77761619
137 84503164
138 91791454
139 99682573
140 108234239
141 117473425
142 127469137
143 138291916
144 149978856
145 162611857
146 176280015
147 191030279
148 206963235
149 224187452
150 242765759
151 262817967
152 284479944
153 307830783
154 333017390
155 360204910
156 389497060
157 421069325
158 455126820
159 491799426
160 531301975
161 573883178
162 619710684
163 669041738
164 722183307
165 779344231
166 840838922
167 907038809
168 978210078
169 1054729871
170 1137054174
171 1225512959
172 1320566422
173 1422765188
174 1532525511
175 1650400082
176 1777061802
177 1913024273
178 2058960734
179 2215682251
180 2383831151
181 2564216533
182 2757825653
183 2965447662
184 3188066353
185 3426869594
186 3682837102
187 3957151497
188 4251253663
189 4566342421
190 4903853036
191 5265516316
192 5652811198
193 6067462704
194 6511563821
195 6986917507
196 7495613267
197 8040161183
198 8622773255
199 9245959587
200 9912747076
201 10625822969
202 11388221724
203 12203567873
204 13075142331
205 14006587501
206 15002263143
207 16066142212
208 17202619189
209 18416906768
210 19713834659
211 21098672490
212 22577675800
213 24156675328
214 25842015964
215 27641166108
216 29561186390
217 31609676276
218 33795578982
219 36127394497
220 38614254521
221 41266820813
222 44095350158
223 47110765539
224 50325808411
225 53752793699
226 57404820461
227 61297057015
228 65444316050
229 69862243965
230 74568933369
231 79582124964
232 84920545106
233 90605702221
234 96658872686
235 103102391363
236 109961866935
237 117262721518
238 125031634434
239 133299006952
240 142095245296
241 151452121022
242 161405768445
243 171992437789
244 183250008063
245 195221316959
246 207949612970
247 221479934648
248 235863113546
249 251150601778
250 267395995113
251 284659472930
252 303002276949
253 322488032791
254 343188035529
255 365174997851
256 388524495597
257 413320820878
258 439650331780
259 467602606077
260 497277350726
261 528776903864
262 562207478059
263 597686799185
264 635336160311
265 675281254706
266 717661127845
267 762619256083
268 810304415344
269 860880561822
270 914517416164
271 971390768592
272 1031693983634
273 1095627472964
274 1163398957754
275 1235236146203
276 1311375672648
277 1392062600029
278 1477565096826
279 1568162122899
280 1664142779253
281 1765822454966
282 1873529953620
283 1987605834187
284 2108421008497
285 2236362470920
286 2371831337818
287 2515263275094
288 2667113663875
289 2827854318335
290 2997996904279
291 3178076569561
292 3368648163355
293 3570311919109
294 3783696548628
295 4009453750151
296 4248287527292
297 4500935623146
298 4768163274356
299 5050795315862
300 5349697152316
301 5665766319625
302 5999968993380
303 6353319201631
304 6726869306169
305 7121749920431
306 7539148798087
307 7980298531794
308 8446521785117
309 8939208366475
310 9459801437570
311 10009846898157
312 10590970362359
313 11204859866782
314 11853321646623
315 12538255305793
316 13261634525451
317 14025567876011
318 14832274235459
319 15684059130834
320 16583383212662
321 17532835968572
322 18535109441193
323 19593072784607
324 20709746729454
325 21888271895058
326 23131992505380
327 24444429381207
328 25829244872086
329 27290333890714
330 28831798367222
331 30457905540009
332 32173189908839
333 33982426625893
334 35890585500566
335 37902941729229
336 40025051727883
337 42262699038085
338 44622018040384
339 47109469372279
340 49731780475177
341 52496079801864
342 55409876003173
343 58480988670074
344 61717697944763
345 65128724257529
346 68723152455246
347 72510593927070
348 76501171881442
349 80705433690763
350 85134531255558
351 89800208210654
352 94714704207210
353 99890950167360
354 105342563369276
355 111083737671545
356 117129460325106
357 123495510903549
358 130198341816064
359 137255312804031
360 144684700806705
361 152505563831839
362 160738000896396
363 169403168345164
364 178523132163269
365 188121148889848
366 198221696835654
367 208850308850653
368 220033883235772
369 231800724905589
370 244180364570737
371 257203894497456
372 270904029672341
373 285314904226207
374 300472442534976
375 316414434946764
376 333180318447478
377 350811577184704
378 369351844729134
379 388846658484540
380 409343901831561
381 430893926993566
382 453549291432968
383 477365234834416
384 502399836822050
385 528713723375783
386 556370592830734
387 585437402037868
388 615984052527197
389 648083957779722
390 681814274783290
391 717255556360164
392 754492376191708
393 793613598914974
394 834712010124694
395 877884990340935
396 923234843813279
397 970868390851075
398 1020897709899895
399 1073440517814662
400 1128619738173281
401 1186564301482372
402 1247409600910256
403 1311297019335643
404 1378374809984461
405 1448798620098789
406 1522730992965926
407 1600342317739361
408 1681811449583741
409 1767325167409034
410 1857079218850052
411 1951279029229422
412 2050139134375997
413 2153884308161472
414 2262750394237927
415 2376983692542714
416 2496842199675994
417 2622596555837026
418 2754529408197550
419 2892936750101151
420 3038129023605570
421 3190430436149770
422 3350180433932153
423 3517734952869858
424 3693465716365079
425 3877761827394736
426 4071031215985350
427 4273699892336713
428 4486213698968336
429 4709039948321828
430 4942666664683185
431 5187604479495185
432 5444388516360937
433 5713577593953714
434 5995756312933226
435 6291537183324150
436 6601559828734519
437 6926493246661376
438 7267038246475795
439 7623926625293814
440 7997923658535291
441 8389830845593957
442 8800485106098245
443 9230761481395298
444 9681576269235741
445 10153886209313487
446 10648691462585525
447 11167039135135152
448 11710022512037167
449 12278784294429788
450 12874520609562268
451 13498480261038410
452 14151968302567486
453 14836350538723323
454 15553052863260255
455 16303565149268613
456 17089446356431381
457 17912323925543689
458 18773898078423944
459 19675947542219420
460 20620329087355814
461 21608982217573980
462 22643935649600996
463 23727306964046775
464 24861307796286546
465 26048251090211678
466 27290550968398701
467 28590728406053891
468 29951419424220285
469 31375375151935131
470 32865468114941767
471 34424701397980648
472 36056209028760579
473 37763262867178866
474 39549282934618873
475 41417838098122189
476 43372653717250688
477 45417623184444424
478 47556809068162082
479 49794451508957226
480 52134981208012736
481 54583021016617744
482 57143395269497956
483 59821144284485824
484 62621526592762500
485 65550029209962410
486 68612383931361886
487 71814570203624701
488 75162826559380157
489 78663668795481359
490 82323893724648756
491 86150591787161118
492 90151167453639908
493 94333343876452475
494 98705176950222201
495 103275078058489400
496 108051819917489724
497 113044552117758105
498 118262826625136771
499 123716604863402752
500 129416275064997135
501 135372680686632517
502 141597129090277183
503 148101410761168729
504 154897831132047174
505 161999220945255471
506 169418957735168174
507 177171001273687841
508 185269906055502859
509 193730845138422589
510 202569649805458606
511 211802824304719087
512 221447572529693832
513 231521842177387340
514 242044342286741188
515 253034572899943430
516 264512874434882545
517 276500448218185007
518 289019389714101643
519 302092743475726985
520 315744527342229774
521 329999769439765040
522 344884569579135911
523 360426127398142030
524 376652783849854185
525 393594089518892250
526 411280837533571864
527 429745109829637865
528 449020353434592996
529 469141418541049187
530 490144610420130081
531 512067774282243654
532 534950339527698994
533 558833377707425442
534 583759697230973635
535 609773894328695497
536 636922418130142935
537 665253675999519121
538 694818092461601378
539 725668181938011890
540 757858666250720480
541 791446542229724361
542 826491163419898485
543 863054370749064633
544 901200570360860087
545 940996825016770367
546 982512999798560383
547 1025821851119360989
548 1070999129433144163
549 1118123741239752479
550 1167277851176824102
551 1218546996998699266
552 1272020270155796841
553 1327790432219705602
554 1385954044114175517
555 1446611666877828941
556 1509867994767883687
557 1575832000009435980
558 1644617156504406129
559 1716341591245916606
560 1791128247026578113
561 1869105131129258725
562 1950405487943414848
563 2035167981286918599
564 2123536971442061352
565 2215662711085875948
566 2311701550232727791
567 2411816244184406847
568 2516176176338281390
569 2624957587899111246
570 2738343920841271734
571 2856526070311759048
572 2979702642819033024
573 3108080337441850905
574 3241874232219350111
575 3381308073591578896
576 3526614700852094158
577 3678036370002500906
578 3835825079018732791
579 4000243039611609745
580 4171563043958004249
581 4350068829359082377
582 4536055603406817047
583 4729830458022419167
584 4931712779151417260
585 5142034830433241627
586 5361142221214405623
587 5589394365844503373
588 5827165133295087799
589 6074843374770597028
590 6332833439573402583
591 6601555897053421741
592 6881448132028618326
593 7172964923037993185
594 7476579245719739025
595 7792782943152640592
596 8122087375099671994
597 8465024310791176387
598 8822146684298103172
599 9194029322159389874
600 9581269936691464753
601 9984489975358839873
602 10404335437406065372
603 10841477977648758877
604 11296615862286798347
605 11770474883904863766
606 12263809589345650775
607 12777404353237098763
608 13312074404472762116
609 13868667190574441061
610 14448063584246606355
611 15051179033162965051
612 15678965077457127912
613 16332410703438629407
614 17012543632868584397
615 17720432009021028591
616 18457185916395509952
617 19223958824378849894
618 20021949462238045936
619 20852403522512982965
620 21716615279033453405
621 22615929670040018736
622 23551744208414529753
623 24525510792771899256
624 25538738023630055261
625 26592993342555296539
626 27689905060962232492
627 28831164933166817529
628 30018530552907313797
629 31253827623322355975
630 32538952817394222027
631 33875876459353801999
632 35266645066212374745
633 36713384525153152003
634 38218303094783538974
635 39783694247585053484
636 41411940201601436600
637 43105515275752521344
638 44866989070642442009
639 46699030391160824658
640 48604410998790648150
641 50586009167442236320
642 52646814042692040821
643 54789929833568449010
644 57018579789537317301
645 59336111041690930822
646 61745999286705512723
647 64251853230681265071
648 66857419968258803374
649 69566590211418684330
650 72383403256973037480
651 75312052959626160723
652 78356893570260191518
653 81522445283945044377
654 84813400875466184931
655 88234632212300518181
656 91791196453043599939
657 95488343414585590521
658 99331522839043930287
659 103326391313250142100
660 107478820451442909693
661 111794904996767710348
662 116280970547796958052
663 120943582642097390663
664 125789555789445512289
665 130825962093000970145
666 136060141336381069450
667 141499711048120118641
668 147152576123178087148
669 153026940018739884515
670 159131315968924397629
671 165474537715147477198
672 172065771936212325115
673 178914530736004420927
674 186030683612536929891
675 193424471251913617019
676 201106519434715767001
677 209087852377946452896
678 217379908046449762564
679 225994553629171010774
680 234944100413390005621
681 244241320773041998201
682 253899465393156224983
683 263932279842157476522
684 274354023424885082440
685 285179488341224012520
686 296424018152032133027
687 308103528692879377281
688 320234529384954935167
689 332834143799125921086
690 345920132859950422182
691 359510918537493719464
692 373625606749292745089
693 388284013095428306424
694 403506689197846033985
695 419314948192200071928
696 435730893274478863520
697 452777446968565152746
698 470478379501753634870
699 488858340458455052613
700 507942891301721088641
701 527758536942534529575
702 548332760843197842162
703 569694061137199834207
704 591871985752024010508
705 614897171324634465446
706 638801383317441711392
707 663617555075835649078
708 689379830974067771823
709 716123610949372141419
710 743885593934429120567
711 772703825677728248741
712 802617748181300113593
713 833668247976227774073
714 865897709127983291883
715 899350068094565319474
716 934070867383358614189
717 970107314285176954144
718 1007508341744974517784
719 1046324667974300817277
720 1086608861536774076218
721 1128415408863619935760
722 1171800780479532872108
723 1216823503104805981824
724 1263544234537640312513
725 1312025837197148491868
726 1362333458001412376470
727 1414534611389423750225
728 1468699260984544938841
729 1524899908061740141852
730 1583211683588824009712
731 1643712438871969101341
732 1706482843537421320661
733 1771606487536027773196
734 1839169981751136528409
735 1909263066488251818320
736 1981978724514123397987
737 2057413292680904172668
738 2135666582050841575977
739 2216842003121985170985
740 2301046689664192365649
741 2388391631691557368264
742 2478991814178639778472
743 2572966354396199838570
744 2670438649103550695135
745 2771536528160239943318
746 2876392406818639211092
747 2985143448615473168237
748 3097931735465111988925
749 3214904436481491509320
750 3336213988238519682957
751 3462018283057009868950
752 3592480856130627276716
753 3727771084958269409929
754 3868064397753085445303
755 4013542480790766804819
756 4164393499044549101852
757 4320812326801046412791
758 4483000777390945023343
759 4651167847222904704921
760 4825529970949506689216
761 5006311275918624072558
762 5193743852074520018205
763 5388068034210655016479
764 5589532683769119960592
765 5798395487282254833598
766 6014923268558135647128
767 6239392300675923886445
768 6472088635966649867486
769 6713308451215986018714
770 6963358393049261895772
771 7222555942703151054041
772 7491229797699925670528
773 7769720254087880705776
774 8058379609644873822079
775 8357572585772273403193
776 8667676750470496124921
777 8989082963927005419525
778 9322195844820261261276
779 9667434238244810238543
780 10025231708102141974368
781 10396037052366150658877
782 10780314820667764017513
783 11178545858289955601890
784 11591227875475203418364
785 12018876019790665648135
786 12462023477086235366625
787 12921222100367300500989
788 13397043042654809057503
789 13890077420734705056771
790 14400937009752362979899
791 14930254942785541732162
792 15478686443881148611880
793 16046909595069567102317
794 16635626109579027496365
795 17245562141230121409057
796 17877469131326019400377
797 18532124663052789609937
798 19210333355101541199317
799 19912927796552383020461
800 20640769490856182881334
801 21394749842255977181590
802 22175791187689688858682
803 22984847839500917302325
804 23822907174188692174317
805 24690990771161099076895
806 25590155564341903659508
807 26521495043633574519565
808 27486140511440060658090
809 28485262354252828477336
810 29520071368358790226283
811 30591820146033284162310
812 31701804479409861698212
813 32851364823006943997421
814 34041887822792423091759
815 35274807865757367589707
816 36551608693208649293289
817 37873825087101617435710
818 39243044580200024221734
819 40660909235349162523922
820 42129117505029977993458
821 43649426118343717643322
822 45223652043125028164669
823 46853674536122042353387
824 48541437224795393551047
825 50288950270669715968829
826 52098292629408245502736
827 53971614347062029606034
828 55911138945028216624613
829 57919165911047734857497
830 59998073231637617711532
831 62150320020891069484921
832 64378449265658296726893
833 66685090617890576817730
834 69072963291876077274099
835 71544879088996027904433
836 74103745476220252520643
837 76752568778634002964418
838 79494457511832863727149
839 82332625775226090319709
840 85270396769534232758990
841 88311206467466180857814
842 91458607353493038581270
843 94716272298732685464361
844 98087998603749485588016
845 101577712119384520475674
846 105189471514824622646834
847 108927472729484013718724
848 112796053513075473302248
849 116799698125969162922214
850 120943042240941424824803
851 125230877944203481477175
852 129668158911202690541996
853 134260005802789942035432
854 139011711773229482429802
855 143928748168589745862212
856 149016770466458460983378
857 154281624341220748720693
858 159729351937030099008316
859 165366198404744071433650
860 171198618579911321808493
861 177233283887132473326340
862 183477089533365245127240
863 189937161859202804098869
864 196620865937229090051976
865 203535813486319115420662
866 210689870962955959454256
867 218091167921993905373357
868 225748105723128669479912
869 233669366435195567823098
870 241863922034685197888619
871 250341043982154310031644
872 259110313019820621322193
873 268181629290171283366396
874 277565222867915547585700
875 287271664538649775072863
876 297311876928187603941870
877 307697146083592594066530
878 318439133329502259205125
879 329549887507226433421103
880 341041857707758218131224
881 352927906311316779888049
882 365221322445169391853787
883 377935835981062144927088
884 391085631874077987450276
885 404685364958258490318272
886 418750175332081337795490
887 433295704123512117962734
888 448338109754344388434011
889 463894084848816367386239
890 479980873564325541869081
891 496616289467564244142730
892 513818734114731015973038
893 531607216100325940609353
894 550001370702307948072278
895 569021480296120951083605
896 588688495289027800984647
897 609024055706111692140995
898 630050513616296735227962
899 651790956135218011010745
900 674269229140788724978987
901 697509961905907920869093
902 721538592370824225051717
903 746381393194500026618078
904 772065498807753584423023
905 798618933174709347273858
906 826070638406367889362904
907 854450504467726098317866
908 883789399669346979289644
909 914119202090533962778610
910 945472832196715133828361
911 977884286324497656533189
912 1011388671185928384875671
913 1046022239676144753155524
914 1081822427640864340342757
915 1118827891758358472742634
916 1157078548844506935767113
917 1196615616218417776359343
918 1237481653287475774370213
919 1279720604685332689143490
920 1323377844581873891834312
921 1368500222326805727422661
922 1415136109788476908204160
923 1463335449986416362489967
924 1513149807183196851292408
925 1564632418825956542654585
926 1617838248916129310727514
927 1672824042975335689990150
928 1729648385030061079878133
929 1788371756171482187392286
930 1849056594862000369620215
931 1911767359444156058851587
932 1976570592386842397241407
933 2043534986442155261090632
934 2112731453205614633045142
935 2184233193590815340890446
936 2258115770394971952300080
937 2334457183486062804172345
938 2413337947099669078665374
939 2494841169423044434568734
940 2579052635039592743251173
941 2666060889696309132555339
942 2755957327574230362273296
943 2848836281678634633228884
944 2944795116787083532854056
945 3043934325135552356768751
946 3146357625508001082326685
947 3252172065140276052765583
948 3361488124620325894795017
949 3474419826499995056135721
950 3591084847003375084263079
951 3711604631012844051718720
952 3836104511103629761038070
953 3964713829983067628339178
954 4097566066516472506762617
955 4234798966167572485574673
956 4376554675182413861244525
957 4522979878696546232066158
958 4674225943656892797618711
959 4830449065856900565216611
960 4991810421264424968012164
961 5158476322599029294877397
962 5330618380428828798219285
963 5508413668962741001278857
964 5692044897567206530620610
965 5881700587245848843109705
966 6077575252256221824296708
967 6279869587967232101568510
968 6488790664166250222967925
969 6704552123984736757905594
970 6927374389628455215382040
971 7157484874088505729725453
972 7395118198998700487792411
973 7640516419910345039799138
974 7893929258130509103273352
975 8155614339281986346522342
976 8425837439949916652611956
977 8704872741527569360933701
978 8993003091414336223932209
979 9290520273027747997536262
980 9597725283711556463129282
981 9914928620683321751586856
982 10242450576590143673847256
983 10580621543720606375190061
984 10929782327009109790159436
985 11290284467511469593140220
986 11662490575369598196585387
987 12046774672389237196091032
988 12443522546031043805199608
989 12853132113799026791461735
990 13276013798140636417910716
991 13712590913784209635554290
992 14163300066468355585848432
993 14628591563162467202242209
994 15108929835841971734803139
995 15604793877739937031442517
996 16116677692161860635462388
997 16645090756069786732573059
998 17190558497329617767819670
999 17753622785690082423293688
1000 18334842439856043905686098