0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 14
8 22
9 29
10 41
11 54
12 75
13 97
14 130
15 168
16 222
17 283
18 368
19 465
20 597
21 750
22 949
23 1183
24 1488
25 1841
26 2292
27 2822
28 3487
29 4267
30 5239
31 6376
32 7782
33 9429
34 11439
35 13798
36 16661
37 20007
38 24043
39 28763
40 34420
41 41021
42 48894
43 58066
44 68956
45 81627
46 96592
47 113981
48 134458
49 158190
50 186030
51 218263
52 255936
53 299478
54 350221
55 408759
56 476796
57 555157
58 645963
59 750392
60 871127
61 1009718
62 1169567
63 1352800
64 1563658
65 1804976
66 2082103
67 2398772
68 2761723
69 3175862
70 3649590
71 4189371
72 4805756
73 5507042
74 6306469
75 7214828
76 8248575
77 9421603
78 10754493
79 12264976
80 13978765
81 15918457
82 18115968
83 20600134
84 23410648
85 26583884
86 30169190
87 34212569
88 38775103
89 43914682
90 49706998
91 56224635
92 63561242
93 71807680
94 81079440
95 91490101
96 103182162
97 116296799
98 131009625
99 147496215
100 165972326
101 186655675
102 209811350
103 235708569
104 264672627
105 297035884
106 333196594
107 373564571
108 418627122
109 468887915
110 524942540
111 587409574
112 657015518
113 734518525
114 820804148
115 916799837
116 1023583666
117 1142288558
118 1274224832
119 1420774564
120 1583529005
121 1764170556
122 1964629360
123 2186951542
124 2433474695
125 2706683338
126 3009406090
127 3344655097
128 3715849311
129 4126635927
130 4581141782
131 5083777857
132 5639520688
133 6253696527
134 6932300164
135 7681756452
136 8509277793
137 9422604175
138 10430404828
139 11541992365
140 12767776096
141 14118948211
142 15607993139
143 17248347416
144 19054970317
145 21043972295
146 23233260226
147 25642131904
148 28291999509
149 31205953190
150 34409573448
151 37930457981
152 41799137793
153 46048564951
154 50715142427
155 55838177160
156 61461034767
157 67630552716
158 74398344010
159 81820168460
160 89957396708
161 98876346283
162 108649927535
163 119356939800
164 131083926810
165 143924434124
166 157981096427
167 173364866531
168 190197360848
169 208610056983
170 228746942742
171 250763686833
172 274830618294
173 301131888732
174 329868826471
175 361259091833
176 395540462782
177 432969994396
178 473828286024
179 518418673183
180 567072032715
181 620146018917
182 678030494397
183 741146833389
184 809954044484
185 884948186508
186 966669277083
187 1055700847435
188 1152677750829
189 1258285900871
190 1373271089985
191 1498438982808
192 1634665071563
193 1782894977070
194 1944155717269
195 2119556392542
196 2310300918457
197 2517689211120
198 2743131584058
199 2988150527299
200 3254397008634
201 3543652975124
202 3857849801707
203 4199071695169
204 4569576566742
205 4971800503523
206 5408381427714
207 5882164844605
208 6396230633878
209 6953900353717
210 7558767593813
211 8214707105890
212 8925909222399
213 9696891153538
214 10532536004784
215 11438106671730
216 12419290067856
217 13482214052911
218 14633497629910
219 15880271439483
220 17230234691696
221 18691679893431
222 20273557439529
223 21985505261633
224 23837922156066
225 25842003184032
226 28009822902224
227 30354377527502
228 32889679398470
229 35630806983111
230 38594012172602
231 41796779407194
232 45257947491122
233 48997779373428
234 53038100474064
235 57402380777345
236 62115891963524
237 67205803766978
238 72701362440696
239 78634003690540
240 85037555352642
241 91948369431898
242 99405552383696
243 107451119206196
244 116130254991473
245 125491494545276
246 135587019471423
247 146472867136260
248 158209268177305
249 170860889243979
250 184497216365060
251 199192836637833
252 215027873626048
253 232088313736654
254 250466500819731
255 270261513845936
256 291579728595624
257 314535254311727
258 339250571553012
259 365857036367218
260 394495604657615
261 425317413706042
262 458484604627153
263 494170992571483
264 532563000398537
265 573860430225960
266 618277523420912
267 666043848000656
268 717405501696406
269 772626131879285
270 831988300849394
271 895794656948588
272 964369483847007
273 1038060044165857
274 1117238337178250
275 1202302639350115
276 1293679498092486
277 1391825496609860
278 1497229515270453
279 1610414751949139
280 1731941286249653
281 1862408390950507
282 2002457439141407
283 2152774546754280
284 2314093868002165
285 2487200614459896
286 2672934789794046
287 2872194637128448
288 3085940870684479
289 3315200609574090
290 3561072171810523
291 3824729560495742
292 4107427893462122
293 4410508516797346
294 4735405153115617
295 5083649726626544
296 5456879323846294
297 5856842825602566
298 6285408785583371
299 6744572977404426
300 7236467309860473
301 7763368410606932
302 8327707712647173
303 8932081212064219
304 9579260876525044
305 10272205732598649
306 11014074766564899
307 11808239516098695
308 12658298655387583
309 13568092288582528
310 14541718434880262
311 15583549246727303
312 16698249637673685
313 17890795675868338
314 19166495628632671
315 20531010813797803
316 21990379368082483
317 23551039875054679
318 25219858203265402
319 27004154268782479
320 28911732332379394
321 30950911299883595
322 33130558915296821
323 35460126053259331
324 37949685299113698
325 40609969743438876
326 43452416501666733
327 46489210584422186
328 49733333975924619
329 53198615225781307
330 56899784782224320
331 60852531029634532
332 65073562658374210
333 69580671962148142
334 74392805120838770
335 79530133672706236
336 85014133693654770
337 90867666470147607
338 97115067679247245
339 103782238414108780
340 110896745601259171
341 118487924672042105
342 126586992604319430
343 135227163688929370
344 144443776751138076
345 154274425637646404
346 164759102359295063
347 175940344121919852
348 187863394341321734
349 200576368259558948
350 214130434018872531
351 228579999151393215
352 243982914157880398
353 260400682434840091
354 277898689097177706
355 296546437211658227
356 316417804929511694
357 337591311238733300
358 360150404835342948
359 384183762991132936
360 409785615998942816
361 437056083177607899
362 466101537182337014
363 497034981646287946
364 529976460150149514
365 565053480533589720
366 602401473884187257
367 642164271142921565
368 684494618103131819
369 729554710597199649
370 777516772195993864
371 828563655003798117
372 882889487531124395
373 940700348944856359
374 1002214995461813922
375 1067665616818905541
376 1137298650502076971
377 1211375630225032939
378 1290174098391925468
379 1373988557507735411
380 1463131492479014139
381 1557934437147572667
382 1658749119372179789
383 1765948656290407315
384 1879928836617391382
385 2001109459807528061
386 2129935771671352406
387 2266879964357880539
388 2412442783233947359
389 2567155206555518795
390 2731580243612573518
391 2906314815116399961
392 3091991764901589255
393 3289281964463736136
394 3498896563049188839
395 3721589342455469205
396 3958159233166160427
397 4209452948495030434
398 4476367797569343591
399 4759854631204908272
400 5060920986024924024
401 5380634378128853593
402 5720125816514792707
403 6080593484678562257
404 6463306665816676208
405 6869609857024883907
406 7300927153536986664
407 7758766845226844000
408 8244726312448618968
409 8760497160125441562
410 9307870683656425714
411 9888743602076922536
412 10505124159029852164
413 11159138523367148063
414 11853037597444528640
415 12589204161159472425
416 13370160467882273301
417 14198576216396038916
418 15077277023700041207
419 16009253318712986743
420 16997669791086383836
421 18045875310937022213
422 19157413463792581479
423 20336033612165338138
424 21585702638908357444
425 22910617279243075859
426 24315217208293449168
427 25804198786348854176
428 27382529641287161208
429 29055463985566669476
430 30828558860791653466
431 32707691202334165152
432 34699075931626707237
433 36809284963575906315
434 39045267352474535768
435 41414370458711605970
436 43924362376654355174
437 46583455500791031908
438 49400331488815804522
439 52384167493476492914
440 55544663941630366793
441 58892073727010767631
442 62437233116474257716
443 66191594230925510492
444 70167259423677656192
445 74377017412180136989
446 78834381510702273261
447 83553629814686765006
448 88549847711171404486
449 93838972560919966646
450 99437840955585065489
451 105364238390646803170
452 111636951788713285278
453 118275824709246080082
454 125301815713074791878
455 132737059713411595767
456 140604932818202290217
457 148930120491572682810
458 157738689578653544807
459 167058164018041351277
460 176917604828829403873
461 187347694193585048875
462 198380824270297054266
463 210051190552497095148
464 222394890460461245953
465 235450026981338871228
466 249256818095087283822
467 263857711803722397951
468 279297507559135237639
469 295623483907825856707
470 312885533211019521315
471 331136303260674227809
472 350431346718293535271
473 370829278200824129651
474 392391940014638111047
475 415184576367467554329
476 439276017139579126996
477 464738871051696405343
478 491649729397952630255
479 520089380191442126585
480 550143033984886348778
481 581900561226785762500
482 615456742517760592183
483 650911531643305919937
484 688370332858465208151
485 727944292320076893815
486 769750605262205049396
487 813912838833833475759
488 860561272324762514313
489 909833254726681567601
490 961873581496763526401
491 1016834890503780036195
492 1074878079177477627908
493 1136172742879995566604
494 1200897636686611182708
495 1269241160639758225239
496 1341401870844422100708
497 1417589016521325827280
498 1498023105582286610882
499 1582936498904747735098
500 1672574036083094567980
501 1767193692903386295703
502 1867067273550747808432
503 1972481137875898754655
504 2083736966981661060732
505 2201152567547150713507
506 2325062718423967789536
507 2455820060025911086037
508 2593796030343777080562
509 2739381848224801563099
510 2892989548071347764388
511 3055053066732176260097
512 3226029387092208751124
513 3406399739285342869282
514 3596670864418268643002
515 3797376341900605177721
516 4009077985684725913588
517 4232367310703022060684
518 4467867075257936752206
519 4716232900868866544156
520 4978154975822990225131
521 5254359844177216586258
522 5545612286993253628020
523 5852717297825636734676
524 6176522159826962174390
525 6517918626795454734922
526 6877845216162839820655
527 7257289616589264020698
528 7657291218852947887567
529 8078943773083075238073
530 8523398181774571255189
531 8991865432059258468275
532 9485619677489708970901
533 10006001473285423470577
534 10554421176187886913178
535 11132362513403451588327
536 11741386332750200198424
537 12383134539076766432136
538 13059334230125311788086
539 13771802037561787633802
540 14522448687495820648090
541 15313283786941392213027
542 16146420851793663140697
543 17024082583581315622313
544 17948606411934854045960
545 18922450310927134112805
546 19948198907713678318260
547 21028569892623513717199
548 22166420750748587711031
549 23364755825284277516722
550 24626733734434874611666
551 25955675153356769281535
552 27355070984877321595789
553 28828590931812616132608
554 30380092496719139212394
555 32013630423396090047128
556 33733466608258888747095
557 35544080497551848718947
558 37450180001011393152243
559 39456712939772267815596
560 41568879061843213419323
561 43792142644959238854385
562 46132245723096448205004
563 48595221958680590152573
564 51187411200001036141746
565 53915474748315227344751
566 56786411377671825914752
567 59807574134643530206922
568 62986687964831233512791
569 66331868196313620185773
570 69851639931082594436756
571 73554958377925758180758
572 77451230182352014570421
573 81550335790641928714457
574 85862652908585435770789
575 90399081095974959063697
576 95171067562830666483833
577 100190634212813606145463
578 105470406005706154547028
579 111023640689242670486901
580 116864259978604947498210
581 123006882239174847139157
582 129466856757873977126971
583 136260299664520515950164
584 143404131596181339782745
585 150916117172365667447732
586 158814906382376490640491
587 167120077959716164760182
588 175852184853952085507557
589 185032801882683134809875
590 194684575683922324174913
591 204831277060040049905636
592 215497855844386234224016
593 226710498391071530575173
594 238496687830801901237557
595 250885267203492646812175
596 263906505623393591680751
597 277592167598692821658181
598 291975585675324417125191
599 307091736539278426986202
600 322977320762391857780076
601 339670846339441158372966
602 357212716218141624920080
603 375645319984698514813996
604 395013129924637970496165
605 415362801637811323578031
606 436743279447052920525579
607 459205906797190349155174
608 482804541905415274676634
609 507595678879219636793137
610 533638574586367860430503
611 560995381514474631354335
612 589731286930227830009867
613 619914658599221505475914
614 651617197404302867224265
615 684914097149010548122677
616 719884211914372193111084
617 756610231283673361413519
618 795178863836551504374446
619 835681029257706082236603
620 878212059497629262155699
621 922871909364213578029732
622 969765377021919804632333
623 1019002334814078136694150
624 1070697970927798875263057
625 1124973042357221348330207
626 1181954139731197471098852
627 1241773964505045745745670
628 1304571619133258432778767
629 1370492910770799052692968
630 1439690669175193574739927
631 1512325079409519223306849
632 1588564030078751875664110
633 1668583477756912259288236
634 1752567828403102458182637
635 1840710336486520616076232
636 1933213522690022442992261
637 2030289610980755877418860
638 2132160985995278592549190
639 2239060671602434846562881
640 2351232831676166852477697
641 2468933294023168928762892
642 2592430098589858213814419
643 2722004070982701010274907
644 2857949422526864728357359
645 3000574377994536090146039
646 3150201832337289076146946
647 3307170037660048830151922
648 3471833321890147605664627
649 3644562840494923934849216
650 3825747362831025320597576
651 4015794094605334087741529
652 4215129538171816260651102
653 4424200392282188441325247
654 4643474493168320486872520
655 4873441798724773588100165
656 5114615417836580958428830
657 5367532686784816179715520
658 5632756294957001732098168
659 5910875461973900291289886
660 6202507168657728496648594
661 6508297444148499482911944
662 6828922711808963261004065
663 7165091196437607977512371
664 7517544395664580306717192
665 7887058618281892889453129
666 8274446592637773196631704
667 8680559148099260385574707
668 9106286972990300305773595
669 9552562452284848920554021
670 10020361588763972381198631
671 10510706011216515722856303
672 11024665073720517050338831
673 11563358049911820543887736
674 12127956426633997341826820
675 12719686301232074777974940
676 13339830887272343677942132
677 13989733133338510498174800
678 14670798460108549057931177
679 15384497620784771581237461
680 16132369690540414052634163
681 16916025190514999758570078
682 17737149352520747184171753
683 18597505530492787734497216
684 19498938765387906325641628
685 20443379510109370967349339
686 21432847521752229771544856
687 22469455928339583178969128
688 23555415477985149174802023
689 24693038978297888256898365
690 25884745934660617024130220
691 27133067395900479065539020
692 28440651016740261082731185
693 29810266346312278060663867
694 31244810352946496797042956
695 32747313195345562523536061
696 34320944251252311725373028
697 35969018414626242636827532
698 37695002673405762589681292
699 39502522979855623366393311
700 41395371426631518942137432
701 43377513741630134746778932
702 45453097115902847581982563
703 47626458378863554164469630
704 49902132536313880643664391
705 52284861686779744963215453
706 54779604333034809439636507
707 57391545105678268585091538
708 60126104917111132898985075
709 62988951564271304272922370
710 65986010800066442659690156
711 69123477893487332598138118
712 72407829700072499949685573
713 75845837264469812256672062
714 79444578978646063605349625
715 83211454319405880414207441
716 87154198190812263727487312
717 91280895897251253214494204
718 95599998774949010674888453
719 100120340509944562339980893
720 104851154172731881823886588
721 109802090000030138683858922
722 114983233956506549867527561
723 120405127109577568518690218
724 126078785852946261465664956
725 132015723014897721074422196
726 138227969890085154884251963
727 144728099233973165138312368
728 151529249262007313893757984
729 158645148696090668255539919
730 166090142904056484842749945
731 173879221178424136017805741
732 182028045204054875565525592
733 190552978765017762627271812
734 199471118744542894065070187
735 208800327472738901439600610
736 218559266480573380620963912
737 228767431719532096073558424
738 239445190310468254860071960
739 250613818886200020418219045
740 262295543596803936012275691
741 274513581847741963392684320
742 287292185845665239066353887
743 300656688028085554605174988
744 314633548458150360662817325
745 329250404267278922093005984
746 344536121233826741714507640
747 360520847587658620296195724
748 377236070136312140182752904
749 394714672810357128681573846
750 412990997731779299699859041
751 432100908911371376477714873
752 452081858687790407939042712
753 472972957023349097760710999
754 494815043778771098423217213
755 517650764091828033581429453
756 541524646992461404845107679
757 566483187389985954917335372
758 592574931576219056717639735
759 619850566391708978130186944
760 648363012211087836584927270
761 678167519907270056034005790
762 709321771963720655987724632
763 741885987908114069377296706
764 775923034250907353628042540
765 811498539116887054595806831
766 848681011768704665252171548
767 887541967226430999206557948
768 928156056198924895695339568
769 970601200548351546119480908
770 1014958734521821526332135649
771 1061313551990234323479587391
772 1109754259947982631389737122
773 1160373338533911745543260143
774 1213267307848508600916026577
775 1268536901849715438177582014
776 1326287249625427538801699778
777 1386628064348899187308023305
778 1449673840240113113941096949
779 1515544057865144854391787074
780 1584363398123639904590432775
781 1656261965284382107879806269
782 1731375519448369045724685448
783 1809845718829634201668214920
784 1891820372264946793592550869
785 1977453702375393380480892749
786 2066906619825301047691654592
787 2160347009136977405127389334
788 2257950026543882231081538155
789 2359898410379104041557848889
790 2466382804521966872022895408
791 2577602095441203294415601544
792 2693763763401032471935668644
793 2815084248413563494825107024
794 2941789331550946823760770258
795 3074114532249377069375634148
796 3212305522269313225604147075
797 3356618556996700794273358023
798 3507320924804676242905944630
799 3664691415217540965343712275
800 3829020806656107168003879441
801 4000612374567876153424727575
802 4179782420785644424713758784
803 4366860824984718800380385352
804 4562191619152092208241025923
805 4766133586009936247073473556
806 4979060882382205062957098949
807 5201363688524774750784194783
808 5433448884489499258717071743
809 5675740754627042250637052392
810 5928681721387088982277183708
811 6192733109612111407362763700
812 6468375942578682438211199706
813 6756111771081256708770482542
814 7056463536915548580444441745
815 7369976472163194747064674313
816 7697219035746329413462826892
817 8038783888769197777074120688
818 8395288910235963803469774059
819 8767378254786637903848546909
820 9155723454170560275113612512
821 9561024564234274695375843920
822 9984011359284037750627853536
823 10425444575745623373619187523
824 10886117207133845204759023383
825 11366855852412067648538072115
826 11868522119918578685572453896
827 12392014089110430573611710164
828 12938267832479320715703795147
829 13508259000074190286379198036
830 14103004469177112935451146990
831 14723564061766050019534327386
832 15371042332518480010149428470
833 16046590430204381473902114311
834 16751408035446671050877789035
835 17486745377929751489359003500
836 18253905336276342153805152015
837 19054245623924063164399080514
838 19889181064483415404154017489
839 20760185960179558583645413396
840 21668796557141930665104867112
841 22616613611436746175517320032
842 23605305059911400835293022639
843 24636608800061872787510268319
844 25712335583321495284818524386
845 26834372026323507726981994673
846 28004683744891389215115677693
847 29225318615677951810035995833
848 30498410170591176431698040310
849 31826181129325736849443975464
850 33210947075552750789171215510
851 34655120282516380450638023049
852 36161213694037355302255766520
853 37731845067135914405844216948
854 39369741282757339015294541313
855 41077742831313327922021083512
856 42858808480043834365618226907
857 44716020129453142033344065572
858 46652587866387598567045182965
859 48671855221592191596585491373
860 50777304639920769826143678455
861 52972563171666736851856868414
862 55261408393844470939906955235
863 57647774570567787430832235569
864 60135759062062964481700476486
865 62729628992195873220887151032
866 65433828184813856033301200972
867 68252984379573042031940043934
868 71191916738375070970821809004
869 74255643653937496233975956907
870 77449390872510053062904737591
871 80778599943181933892389373298
872 84248937006750401298783533272
873 87866301937589269693701322892
874 91636837852521088291430518084
875 95566941001203092698253629013
876 99663271053145461036622313163
877 103932761797027684666443569527
878 108382632268633784750204586470
879 113020398324318656632580846662
880 117853884677622731541214093536
881 122891237417291459604824144963
882 128140937025714812500951270527
883 133611811917492838270599657726
884 139313052518649869249074763330
885 145254225907766382972952304656
886 151445291041176353958337395609
887 157896614585184253836590805817
888 164618987379201691601312504588
889 171623641554574616434126177097
890 178922268334889918694180206554
891 186527036544490856417602946526
892 194450611853026191722614277815
893 202706176784873611087924986818
894 211307451523456880287296337243
895 220268715541572824727432442541
896 229604830090112839964329149227
897 239331261578747527014177120115
898 249464105883508190078075244524
899 260020113617476854217456095345
900 271016716402265433643401879948
901 282472054179343928143364084996
902 294405003601858177036812565624
903 306835207549066125862265467656
904 319783105807222328208998114744
905 333269966962346458883798005011
906 347317921552141565078159931147
907 361949996526060554437436835767
908 377190151064488299013519554560
909 393063313809876004438425800120
910 409595421564782778135513737342
911 426813459513795619397672676661
912 444745503028577999936959259425
913 463420761117471827667848032000
914 482869621583529290648505339837
915 503123697957196208809698415206
916 524215878272505982829150982755
917 546180375758171957021270855920
918 569052781517803199908317010136
919 592870119276195107625741822286
920 617670902271698154765224278627
921 643495192377607329762418017833
922 670384661538797568087847849389
923 698382655612998795846813275142
924 727534260709635151628132893197
925 757886372122567839399586419893
926 789487765956878808735311768429
927 822389173553512741045194096120
928 856643358819679342527461356954
929 892305198576883846701218732476
930 929431766042846402431685141425
931 968082417567844281948928044689
932 1008318882750734931136912627618
933 1050205358064521861836595015937
934 1093808604126405559712790948400
935 1139198046752221385894126176060
936 1186445881940629314009678691628
937 1235627184937762958567746765776
938 1286820023538919473922544476262
939 1340105575789626321036393392855
940 1395568252254736962923130497329
941 1453295823030404924977720604019
942 1513379549680576604788627309165
943 1575914322286317020309206193472
944 1640998801803583892245639590961
945 1708735567932251648734223704440
946 1779231272707036386137159511256
947 1852596800028710028878591633398
948 1928947431362430391682669216965
949 2008403017838343567489966484454
950 2091088158998686315007069356119
951 2177132388444582918366036861060
952 2266670366645482025318118562166
953 2359842081183830714124673385408
954 2456793054718064300211873297550
955 2557674560957378488250287864536
956 2662643848953016108602473710467
957 2771864376021980324563134601573
958 2885506049631194317681814882508
959 3003745478582157934121559657057
960 3126766233849164755589970866708
961 3254759119437088006648823360728
962 3387922453638728488315116218790
963 3526462361085645479063185780956
964 3670593076001419953369691743864
965 3820537257081283379047231769002
966 3976526314438194476713289931922
967 4138800749071565143388204549918
968 4307610505332189288008806016127
969 4483215336874266581007864727931
970 4665885186604057834289553401338
971 4855900581153357145669817116943
972 5053553040425998037554770370952
973 5259145502785666775689351356118
974 5472992766474817679152717281308
975 5695421947876053228746027917774
976 5926772957250452517655421804444
977 6167398992610523767436788725584
978 6417667052410294029571505139033
979 6677958467759985890518988330210
980 6948669454899411145470071861712
981 7230211688691021738847512494264
982 7523012897922216409531928053811
983 7827517483235323977389426177445
984 8144187158534465391505322018127
985 8473501616749479945668928547492
986 8815959220870160857891420165166
987 9172077721197348917179007317037
988 9542394999792938127343328312771
989 9927469843146642030975757068467
990 10327882744115498955726812953502
991 10744236734230563871976686037456
992 11177158247506180272414889492440
993 11627298016928566381130024838197
994 12095332004844417569293414567335
995 12581962368514650221373810935307
996 13087918462145622242398710520554
997 13613957876757897535195620556097
998 14160867519303310531758540418550
999 14729464732492370447238000059786
1000 15320598456848465955070226411130