0 1
1 1
2 2
3 6
4 21
5 74
6 245
7 744
8 2068
9 5296
10 12608
11 28150
12 59412
13 119341
14 229477
15 424478
16 758491
17 1313931
18 2213350
19 3635214
20 5834559
21 9169668
22 14136101
23 21409620
24 31899782
25 46816226
26 67749956
27 96772222
28 136553926
29 190508831
30 262964229
31 359363130
32 486502469
33 652812293
34 868681386
35 1146835318
36 1502773465
37 1955272142
38 2526961621
39 3244985472
40 4141751368
41 5255783236
42 6632685416
43 8326230310
44 10399581864
45 12926668129
46 15993717093
47 19700970966
48 24164595135
49 29518799087
50 35918187726
51 43540362686
52 52588794467
53 63295987496
54 75926961541
55 90783074284
56 108206211290
57 128583371094
58 152351674668
59 180003830126
60 212094085178
61 249244701555
62 292152987397
63 341598925426
64 398453436617
65 463687321033
66 538380919506
67 623734541926
68 721079710045
69 831891264914
70 957800391349
71 1100608614168
72 1262302823356
73 1445071387800
74 1651321419792
75 1883697255126
76 2145100216316
77 2438709729237
78 2768005866341
79 3136793392526
80 3549227392739
81 4009840563475
82 4523572253494
83 5095799342318
84 5732369048391
85 6439633762188
86 7224488003045
87 8094407602052
88 9057491217006
89 10122504289162
90 11298925555348
91 12596996232926
92 14027771999086
93 15603177890055
94 17336066249989
95 19240277863594
96 21330706410893
97 23623366387021
98 26135464634490
99 28885475640022
100 31893220752801
101 35179951485846
102 38768437067157
103 42683056412336
104 46949894695536
105 51596844700844
106 56653713141560
107 62152332140294
108 68126676068368
109 74612983948681
110 81649887631973
111 89278545962310
112 97542785153607
113 106489245605111
114 116167535389982
115 126630390657438
116 137933843195371
117 150137395406896
118 163304202960965
119 177501265383964
120 192799624866114
121 209274573563518
122 227005869683836
123 246077962650830
124 266580227650402
125 288607209868251
126 312258878736901
127 337640892517602
128 364864873550481
129 394048694514321
130 425316776045474
131 458800396073670
132 494638011240869
133 532975590777818
134 573966963221621
135 617774176366408
136 664567870848100
137 714527667773312
138 767842570811616
139 824711383179702
140 885343139955428
141 949957556169341
142 1018785491130981
143 1092069429457150
144 1170063979279339
145 1253036388117659
146 1341267076918918
147 1435050192766926
148 1534694180783695
149 1640522375750932
150 1752873613992101
151 1872102866066356
152 1998581890836822
153 2132699911487026
154 2274864314070756
155 2425501369192254
156 2585056977425430
157 2753997439092719
158 2932810249036293
159 3122004917026586
160 3322113814465493
161 3533693048054165
162 3757323361108042
163 3993611063214646
164 4243188988942697
165 4506717486324318
166 4784885435845461
167 5078411300693216
168 5388044209022360
169 5714565069017364
170 6058787717540104
171 6421560103167718
172 6803765504439416
173 7206323784145585
174 7630192680507237
175 8076369136108726
176 8545890665461711
177 9039836762093567
178 9559330346068846
179 10105539252867966
180 10679677764563059
181 11283008184246840
182 11916842454686469
183 12582543822190668
184 13281528546694826
185 14015267659085478
186 14785288766802380
187 15593177908773422
188 16440581460754826
189 17329208092166467
190 18260830775529733
191 19237288849633106
192 20260490137568601
193 21332413120800345
194 22455109170444914
195 23630704836961574
196 24861404199469293
197 26149491275926306
198 27497332495427125
199 28907379233891192
200 30382170414436876
201 31924335173754216
202 33536595595809712
203 35221769514236566
204 36982773384784076
205 38822625229220389
206 40744447652103525
207 42751470931856494
208 44847036187603443
209 47034598623245091
210 49317730850273238
211 51700126290845870
212 54185602662666327
213 56778105547232156
214 59481712043041637
215 62300634505368548
216 65239224374238526
217 68301976092263386
218 71493531114012980
219 74818682008627614
220 78282376657397694
221 81889722548061143
222 85645991167593221
223 89556622495287690
224 93627229597952797
225 97863603329070301
226 102271717133790746
227 106857731961663382
228 111628001289024561
229 116589076252994086
230 121747710899054869
231 127110867544217360
232 132685722257796544
233 138479670461855868
234 144500332653399256
235 150755560250419398
236 157253441563937760
237 164002307898199257
238 171010739781212261
239 178287573327852582
240 185841906737778263
241 193683106930430471
242 201820816319424446
243 210264959728663390
244 219025751452537339
245 228113702462598464
246 237539627763133893
247 247314653898087036
248 257450226611808530
249 267958118666148302
250 278850437816430876
251 290139634948886926
252 301838512382145202
253 313960232335420331
254 326518325566063621
255 339526700179175874
256 352999650612013345
257 366951866795950369
258 381398443498794818
259 396354889850285446
260 411837139053633333
261 427861558286003050
262 444444958790862837
263 461604606165167016
264 479358230844368052
265 497724038788290128
266 516720722370930816
267 536367471477292406
268 556683984810379700
269 577690481411536589
270 599407712397329509
271 621856972916221918
272 645060114328320251
273 669039556611508395
274 693818300997324582
275 719419942839971726
276 745868684721889631
277 773189349799355172
278 801407395391614501
279 830548926817089556
280 860640711480239654
281 891710193212697730
282 923785506872339844
283 956895493203985918
284 991069713965469286
285 1026338467322852543
286 1062732803518607365
287 1100284540816616442
288 1139026281727896421
289 1178991429520981797
290 1220214205020951018
291 1262729663701117686
292 1306573713071451641
293 1351783130367836910
294 1398395580546315989
295 1446449634586512704
296 1495984788108468968
297 1547041480307174116
298 1599661113209109160
299 1653886071255172262
300 1709759741214395976
301 1767326532432911361
302 1826631897422658917
303 1887722352794391446
304 1950645500539559391
305 2015450049665714959
306 2082185838190117390
307 2150903855496268094
308 2221656265058151043
309 2294496427537000776
310 2369478924255467653
311 2446659581054097580
312 2526095492535091322
313 2607845046698356726
314 2691967949974915692
315 2778525252662776558
316 2867579374770431706
317 2959194132273189651
318 3053434763787600645
319 3150367957669284914
320 3250061879539523049
321 3352586200246018793
322 3458012124263295506
323 3566412418538238950
324 3677861441786350717
325 3792435174244328626
326 3910211247884642741
327 4031268977097828312
328 4155689389848269916
329 4283555259309304376
330 4414951135983523664
331 4549963380314212950
332 4688680195793913244
333 4831191662576152693
334 4977589771596445541
335 5127968459208713038
336 5282423642343336195
337 5441053254193106227
338 5603957280433394806
339 5771237795982922862
340 5942999002311563623
341 6119347265301672876
342 6300391153669497061
343 6486241477953267780
344 6677011330074649614
345 6872816123480266794
346 7073773633870093268
347 7280004040519550046
348 7491629968202213390
349 7708776529720097447
350 7931571369048535301
351 8160144705102743146
352 8394629376133213357
353 8635160884757143661
354 8881877443633171386
355 9134920021786743894
356 9394432391593518785
357 9660561176428250294
358 9933455898986681493
359 10213269030288025456
360 10500156039365682448
361 10794275443653904460
362 11095788860078183032
363 11404861056857201286
364 11721660006024256432
365 12046356936676124713
366 12379126388957406821
367 12720146268788458246
368 13069597903345075815
369 13427666097298178839
370 13794539189821790814
371 14170409112377695518
372 14555471447285209611
373 14949925487084582480
374 15353974294702603077
375 15767824764429062876
376 16191687683712793826
377 16625777795786070302
378 17070313863126234556
379 17525518731763476046
380 17991619396443766274
381 18468847066656022395
382 18957437233532644869
383 19457629737632646818
384 19969668837616665521
385 20493803279823219633
386 21030286368755649250
387 21579376038489249862
388 22141334925008185541
389 22716430439481841402
390 23304934842490350453
391 23907125319209105416
392 24523284055562141956
393 25153698315354356000
394 25798660518392594464
395 26458468319605735734
396 27133424689173953668
397 27823837993677436701
398 28530022078274911845
399 29252296349922401982
400 29990985861642723851
401 30746421397856313531
402 31518939560784046022
403 32308882857932795726
404 33116599790674565231
405 33942444943930090804
406 34786779076967914405
407 35649969215329993844
408 36532388743895004918
409 37434417501090571986
410 38356441874265746468
411 39298854896235136190
412 40262056343006172342
413 41246452832701085071
414 42252457925685243397
415 43280492225913600218
416 44330983483507068661
417 45404366698570741941
418 46501084226265955210
419 47621585883148274614
420 48766329054783585929
421 49935778804654542718
422 51130407984369721941
423 52350697345187923360
424 53597135650870137912
425 54870219791871799476
426 56170454900888024136
427 57498354469764631142
428 58854440467787830296
429 60239243461365551441
430 61653302735113483109
431 63097166414358979190
432 64571391589076084719
433 66076544439265024543
434 67613200361789591726
435 69181944098685966078
436 70783369866956587155
437 72418081489862800472
438 74086692529730090501
439 75789826422279809292
440 77528116612501405258
441 79302206692079252806
442 81112750538388280076
443 82960412455072689070
444 84845867314222159914
445 86769800700160028899
446 88732909054858028293
447 90735899824992274706
448 92779491610655292025
449 94864414315738954617
450 96991409300003336626
451 99161229532846553766
452 101374639748790785037
453 103632416604699763266
454 105935348838743125301
455 108284237431123115064
456 110679895766579235500
457 113123149798686548744
458 115614838215963427568
459 118155812609804665366
460 120746937644255956588
461 123389091227645864645
462 126083164686091499877
463 128830062938894236206
464 131630704675841901587
465 134486022536433984323
466 137396963291046504726
467 140364488024053309486
468 143389572318920654455
469 146473206445292050364
470 149616395548080455269
471 152820159838585007268
472 156085534787649601246
473 159413571320880724090
474 162805336015942073972
475 166261911301943600926
476 169784395660942718046
477 173373903831575545207
478 177031567014836160261
479 180758533082021946186
480 184555966784863236669
481 188425049967855577085
482 192366981782813032794
483 196382978905661092118
484 200474275755487827281
485 204642124715872092998
486 208887796358507659285
487 213212579669142292432
488 217617782275850915936
489 222104730679662101532
490 226674770487557259288
491 231329266647862015046
492 236069603688049383296
493 240897185954974463865
494 245813437857560511589
495 250819804111956349414
496 255917749989185217143
497 261108761565305270311
498 266394345974102066430
499 271776031662333499102
500 277255368647547764251
501 282833928778495066976
502 288513305998153902277
503 294295116609392868156
504 300180999543289095346
505 306172616630124504174
506 312271652873081225820
507 318479816724657652494
508 324798840365826708818
509 331230479987958064971
510 337776516077526140933
511 344438753703625880450
512 351219022808318403137
513 358119178499828773441
514 365141101348618256002
515 372286697686353558278
516 379557899907795693141
517 386956666775631226506
518 394484983728268807925
519 402144863190624015464
520 409938344887915680084
521 417867496162496989168
522 425934412293744803776
523 434141216821030759670
524 442490061869797858132
525 450983128480766389101
526 459622626942293166181
527 468410797125908190622
528 477349908825052999451
529 486442262097045091531
530 495690187608292964454
531 505096046982786434830
532 514662233153887054719
533 524391170719443577668
534 534285316300257569061
535 544347158901924397268
536 554579220280074984390
537 564984055309043838242
538 575564252353989030596
539 586322433646489930622
540 597261255663648646918
541 608383409510721276511
542 619691621307305204741
543 631188652577108846010
544 642877300641330361989
545 654760399015672041029
546 666840817811017170218
547 679121464137796379766
548 691605282514070588185
549 704295255277357826062
550 717194403000231366101
551 730305784909716737536
552 743632499310515353992
553 757177684012082635396
554 770944516759588656616
555 784936215668789508134
556 799156039664837707240
557 813607288925060151969
558 828293305325732264293
559 843217472892877123926
560 858383218257118549503
561 873794011112617239855
562 889453364680119244622
563 905364836174146190526
564 921532027274356847267
565 937958584601109775208
566 954648200195256955781
567 971604612002198464876
568 988831604360228409370
569 1006333008493202507414
570 1024112703007557854124
571 1042174614393715575918
572 1060522717531897238906
573 1079161036202386039475
574 1098093643600263968517
575 1117324662854656304626
576 1136858267552514956041
577 1156698682266972336137
578 1176850183090297622866
579 1197317098171487418726
580 1218103808258522994589
581 1239214747245326468050
582 1260654402723448434869
583 1282427316538519740568
584 1304538085351500248316
585 1326991361204757628888
586 1349791852093009368720
587 1372944322539161362902
588 1396453594175076631356
589 1420324546327307868437
590 1444562116607827708773
591 1469171301509790765326
592 1494157157008361669411
593 1519524799166643516755
594 1545279404746741298614
595 1571426211825995072494
596 1597970520418417803143
597 1624917693101372981196
598 1652273155647527304165
599 1680042397662113882372
600 1708230973225541610926
601 1736844501541386527946
602 1765888667589801158932
603 1795369222786378027486
604 1825291985646503693486
605 1855662842455239861319
606 1886487747942768282885
607 1917772725965436362794
608 1949523870192440556493
609 1981747344798184835981
610 2014449385160351682298
611 2047636298563723249110
612 2081314464909790527457
613 2115490337432188528086
614 2150170443417995684757
615 2185361384934935869488
616 2221069839564521598896
617 2257302561141177199596
618 2294066380497380890040
619 2331368206214864926214
620 2369215025381913149264
621 2407613904356795464393
622 2446571989537378972261
623 2486096508136955666630
624 2526194768966326805127
625 2566874163222184253751
626 2608142165281829300126
627 2650006333504269625502
628 2692474311037735321131
629 2735553826633655030896
630 2779252695467133498949
631 2823578819963971998620
632 2868540190634273316994
633 2914144886912673168318
634 2960401078005240108796
635 3007317023743086225358
636 3054901075442731071650
637 3103161676773261525787
638 3152107364630330446341
639 3201746770017037205602
640 3252088618931733382353
641 3303141733262797100241
642 3354915031690419702306
643 3407417530595448657350
644 3460658344975330799589
645 3514646689367200209434
646 3569391878778155250293
647 3624903329622769483976
648 3681190560667881395620
649 3738263193984708068032
650 3796130955908328154976
651 3854803678004579713206
652 3914291298044418663972
653 3974603860985783866301
654 4035751519963014996581
655 4097744537283869641854
656 4160593285434186227755
657 4224308248090239616219
658 4288900021138836422918
659 4354379313705197319886
660 4420756949188673804943
661 4488043866306347136340
662 4556251120144557348517
663 4625389883218410482996
664 4695471446539312387222
665 4766507220690577653618
666 4838508736911162491236
667 4911487648187570543166
668 4985455730353980884310
669 5060424883200647656239
670 5136407131590621018629
671 5213414626584839320218
672 5291459646575642616341
673 5370554598428757884885
674 5450712018633806517962
675 5531944574463384892726
676 5614265065140769051561
677 5697686423016294749342
678 5782221714752464353621
679 5867884142517832312416
680 5954687045189721133784
681 6042643899565820051540
682 6131768321584718782344
683 6222074067555429010918
684 6313575035395946472376
685 6406285265880906733553
686 6500218943898388008805
687 6595390399715914580022
688 6691814110255714625551
689 6789504700379286498367
690 6888476944181327730158
691 6988745766293081275006
692 7090326243195153744051
693 7193233604539860620920
694 7297483234483153686789
695 7403090673026186123724
696 7510071617366571005418
697 7618441923259389125606
698 7728217606388002356300
699 7839414843744728970542
700 7952049975021437607626
701 8066139504010116802691
702 8181700100013477247237
703 8298748599265644192466
704 8417302006362997653401
705 8537377495705218318489
706 8658992412946597316850
707 8782164276457668243494
708 8906910778797220091693
709 9033249788194749991266
710 9161199350043414901813
711 9290777688403541660920
712 9422003207516755039052
713 9554894493330783705256
714 9689470315035004260912
715 9825749626606783752598
716 9963751568368681329676
717 10103495468556569967461
718 10245000844898739432805
719 10388287406206041925614
720 10533375053973142087219
721 10680283883990933324643
722 10829034187970182658646
723 10979646455176466562990
724 11132141374076460522647
725 11286539833995645299676
726 11442862926787493157221
727 11601131948514197554532
728 11761368401139010089086
729 11923593994230248725786
730 12087830646677041617844
731 12254100488416871089310
732 12422425862174982615294
733 12592829325215723902743
734 12765333651105879442181
735 12939961831490066169098
736 13116737077878256142685
737 13295682823445492419357
738 13476822724843864568986
739 13660180664026810552982
740 13845780750085811955313
741 14033647321099549830246
742 14223804945995588704021
743 14416278426424656541840
744 14611092798647588766464
745 14808273335435004690364
746 15007845547979784999768
747 15209835187822419206086
748 15414268248789292258080
749 15621170968943979786777
750 15830569832551621734501
751 16042491572056444399526
752 16256963170072501208727
753 16474011861387702812231
754 16693665134981207376446
755 16915950736054242234974
756 17140896668074428340795
757 17368531194833679247744
758 17598882842519746634693
759 17831980401801484671996
760 18067852929927905816658
761 18306529752841100910350
762 18548040467303096742812
763 18792414943036724532366
764 19039683324880573065202
765 19289876034958100525803
766 19543023774860979342341
767 19799157527846748663106
768 20058308561050849373025
769 20320508427713116853089
770 20585788969418806980034
771 20854182318354231158918
772 21125720899577076477301
773 21400437433301487366570
774 21678364937197985453557
775 21959536728708304583976
776 22243986427375218298356
777 22531747957187437341072
778 22822855548939655083776
779 23117343742607819046006
780 23415247389739706998004
781 23716601655860886433805
782 24021442022896136506469
783 24329804291606411821918
784 24641724584041427793211
785 24957239346007947563243
786 25276385349553850810790
787 25599199695468065062542
788 25925719815796440442271
789 26255983476373649097572
790 26590028779371190854693
791 26927894165861586962836
792 27269618418398844100966
793 27615240663615271132610
794 27964800374834731407364
795 28318337374702413721854
796 28675891837831205367718
797 29037504293464751009791
798 29403215628157281454085
799 29773067088470296682362
800 30147100283686187848101
801 30525357188538883247461
802 30907880145961603598442
803 31294711869851812281846
804 31685895447853446518841
805 32081474344156515781934
806 32481492402314154058965
807 32885993848077212913344
808 33295023292246482608168
809 33708625733542628887076
810 34126846561493933330728
811 34549731559341925534630
812 34977326906964995681672
813 35409679183820076411201
814 35846835371902483215717
815 36288842858724002926358
816 36735749440309320179231
817 37187603324210872086351
818 37644453132542221667470
819 38106347905030040932414
820 38573337102084794837699
821 39045470607890217676168
822 39522798733511673794181
823 40005372220023494867500
824 40493242241655386304442
825 40986460408957995683126
826 41485078771987736468716
827 41989149823510960596462
828 42498726502227573847066
829 43013862196014188282451
830 43534610745186906352389
831 44061026445783831625650
832 44593164052867401443369
833 45131078783846637137193
834 45674826321819407800466
835 46224462818934803947238
836 46780044899775717741245
837 47341629664761726825202
838 47909274693572379129781
839 48483038048590976391512
840 49062978278368954459548
841 49649154421110958822776
842 50241626008180714141136
843 50840453067627786918230
844 51445696127735340806364
845 52057416220588984390069
846 52675674885666811649893
847 53300534173450735664846
848 53932056649059216469315
849 54570305395901484338547
850 55215344019353360135926
851 55867236650454774715246
852 56526047949629089732007
853 57191843110424322579436
854 57864687863276378527461
855 58544648479294393506244
856 59231791774068291340110
857 59926185111498659602794
858 60627896407649048630868
859 61336994134620798599006
860 62053547324450499928398
861 62777625573030192668135
862 63509299044050410858757
863 64248638472966178257386
864 64995715170986062174957
865 65750601029084392548013
866 66513368522036753740346
867 67284090712478856943446
868 68062841254988901419265
869 68849694400193533204214
870 69644724998897510269589
871 70448008506237183510768
872 71259620985857903315536
873 72079639114115461840780
874 72908140184301681506552
875 73745202110894260597126
876 74590903433830987240176
877 75445323322808433417577
878 76308541581605241044581
879 77180638652430112538246
880 78061695620294618680999
881 78951794217410936971095
882 79851016827614634038494
883 80759446490812606092318
884 81677166907456291754571
885 82604262443040272024208
886 83540818132626372505925
887 84486919685393383429212
888 85442653489212513375266
889 86408106615248693022302
890 87383366822587845613628
891 88368522562890241247566
892 89363662985070052483906
893 90368877940001229158075
894 91384257985249810691589
895 92409894389832794585634
896 93445879139003680183793
897 94492304939064807190001
898 95549265222206608828770
899 96616854151373899936582
900 97695166625159320676101
901 98784298282724056968506
902 99884345508745959143797
903 100995405438395180714376
904 102117575962337459583556
905 103250955731765164407904
906 104395644163456229240480
907 105551741444861099991094
908 106719348539217816649668
909 107898567190695355629661
910 109089499929565357000293
911 110292250077402361788990
912 111506921752312684949067
913 112733619874192050002171
914 113972450170012111780422
915 115223519179135994109518
916 116486934258662969691311
917 117762803588802409862516
918 119051236178277132325285
919 120352341869756275365364
920 121666231345317827494454
921 122993016131940941875218
922 124332808607028165310116
923 125685722003957711998910
924 127051870417665912694262
925 128431368810259970310351
926 129824333016661153465861
927 131230879750278559870042
928 132651126608713581888821
929 134085192079495207057141
930 135533195545846286733834
931 136995257292480906526390
932 138471498511432992544969
933 139962041307916287977918
934 141467008706215834914901
935 142986524655611096778528
936 144520714036330857161080
937 146069702665540031299572
938 147633617303358526859976
939 149212585658912291139942
940 150806736396416682238808
941 152416199141292302184081
942 154041104486313430444901
943 155681583997789196705270
944 157337770221777632213039
945 159009796690332739464799
946 160697797927784720431918
947 162401909457053503979006
948 164122267805995713573075
949 165859010513785216829592
950 167612276137327398890501
951 169382204257707302079116
952 171168935486671774727562
953 172972611473145772524166
954 174793374909782956180876
955 176631369539550729674414
956 178486740162349863769450
957 180359632641668849987619
958 182250193911273130642693
959 184158571981929351019666
960 186084915948164780233913
961 188029375995062047765945
962 189992103405089343127602
963 191973250564966226576806
964 193972970972565199260237
965 195991419243849181626498
966 198028751119845049416501
967 200085123473653377002936
968 202160694317494538316780
969 204255622809791316065864
970 206370069262288170418544
971 208504195147207318794518
972 210658163104441778874796
973 212832136948785527413765
974 215026281677200927908197
975 217240763476123580650926
976 219475749728804749170771
977 221731409022691517535107
978 224007911156844833467286
979 226305427149395592707886
980 228624129245038920526519
981 230964190922566806769660
982 233325786902439251309669
983 235709093154394077240868
984 238114286905095569650206
985 240541546645822098272698
986 242991052140192882825460
987 245462984431934060298782
988 247957525852684213968286
989 250474860029839524378807
990 253015171894438703038213
991 255578647689087870047946
992 258165474975925537386621
993 260775842644627860053565
994 263409940920454317770714
995 266067961372333990433814
996 268750096920992590997393
997 271456541847120419972486
998 274187491799581406211605
999 276943143803663399151952
1000 279723696269369878185376