0 1
1 1
2 2
3 6
4 21
5 73
6 238
7 714
8 1962
9 4957
10 11604
11 25390
12 52361
13 102533
14 191868
15 344970
16 598682
17 1006793
18 1646094
19 2624054
20 4088421
21 6239089
22 9342610
23 13749770
24 19916690
25 28429957
26 40036336
27 55677662
28 76531561
29 104058701
30 140057328
31 186725898
32 246734674
33 323307217
34 420312762
35 542370534
36 694967125
37 884588121
38 1118865238
39 1406740298
40 1758647450
41 2186715117
42 2704989228
43 3329679374
44 4079429609
45 4975615701
46 6042670724
47 7308440970
48 8804574250
49 10566942745
50 12636102662
51 15057793046
52 17883476197
53 21170922241
54 24984840506
55 29397560458
56 34489765058
57 40351279509
58 47081918472
59 54792394942
60 63605294089
61 73656115485
62 85094387256
63 98084855818
64 112808754978
65 129465158305
66 148272418802
67 169469700038
68 193318603029
69 220104893289
70 250140332606
71 283764620234
72 321347448330
73 363290676605
74 410030631300
75 462040533742
76 519833063881
77 583963064357
78 655030390796
79 733682914186
80 820619681338
81 916594239593
82 1022418132094
83 1138964570102
84 1267172288997
85 1408049594769
86 1562678607970
87 1732219712266
88 1917916214898
89 2121099226533
90 2343192768160
91 2585719112862
92 2850304370473
93 3138684323309
94 3452710521344
95 3794356645386
96 4165725146994
97 4569054174065
98 5006724791210
99 5481268504230
100 5995375098197
101 6551900798841
102 7153876767142
103 7804517937226
104 8507232207866
105 9265629998093
106 10083534177628
107 10964990383054
108 11914277730857
109 12935919938677
110 14034696866324
111 15215656488330
112 16484127310026
113 17845731239353
114 19306396926838
115 20872373586390
116 22550245309797
117 24346945888033
118 26269774152714
119 28326409851274
120 30524930069666
121 32873826216629
122 35382021583800
123 38058889496190
124 40914272067785
125 43958499577277
126 47202410479176
127 50657372065802
128 54335301795906
129 58248689305921
130 62410619120098
131 66834794076038
132 71535559482389
133 76527928025737
134 81827605443982
135 87451016983754
136 93415334659690
137 99738505333661
138 106439279632308
139 113537241721518
140 121052839956745
141 129007418428357
142 137423249421468
143 146323566809994
144 155732600404954
145 165675611277321
146 176178928076014
147 187269984361910
148 198977356979045
149 211330805484465
150 224361312658482
151 238101126117386
152 252583801050962
153 267844244107461
154 283918758448976
155 300845090000478
156 318662474916073
157 337411688286349
158 357135094110992
159 377876696561162
160 399682192556434
161 422599025681425
162 446676441467546
163 471965544065638
164 498519354335573
165 526392869379225
166 555643123543542
167 586329250920778
168 618512549373274
169 652256546110509
170 687627064846476
171 724692294565774
172 763522859927145
173 804191893333525
174 846775108698020
175 891350876935562
176 938000303210346
177 986807305969497
178 1037858697793766
179 1091244268096406
180 1147056867701733
181 1205392495335233
182 1266350386057434
183 1330033101674122
184 1396546623155842
185 1466000445099989
186 1538507672269160
187 1614185118239806
188 1693153406195593
189 1775537071900253
190 1861464668885080
191 1951068875886602
192 2044486606570338
193 2141859121576929
194 2243332142927314
195 2349055970824006
196 2459185602885909
197 2573880855854505
198 2693306489809630
199 2817632334933450
200 2947033420861642
201 3081690108661181
202 3221788225474532
203 3367519201870446
204 3519080211941961
205 3676674316192613
206 3840510607252268
207 4010804358464394
208 4187777175387002
209 4371657150249897
210 4562679019411294
211 4761084323857270
212 4967121572787941
213 5181046410334673
214 5403121785453058
215 5633618125036810
216 5872813510298162
217 6120993856460773
218 6378453095811584
219 6645493364158494
220 6922425190741161
221 7209567691642669
222 7507248766750240
223 7815805300313610
224 8135583365150130
225 8466938430546097
226 8810235573904266
227 9165849696187942
228 9534165741212501
229 9915578918835641
230 10310494932098118
231 10719330208367178
232 11142512134535354
233 11580479296327757
234 12033681721771452
235 12502581128880974
236 12987651177614505
237 13489377726155701
238 14008259091576628
239 14544806314937738
240 15099543430881290
241 15673007741775097
242 16265750096463958
243 16878335173686614
244 17511341770216549
245 18165363093785441
246 18841007060848554
247 19538896599251850
248 20259669955861090
249 21003981009213685
250 21772499587254552
251 22565911790217726
252 23384920318715977
253 24230244807101181
254 25102622162158696
255 26002806907199498
256 26931571531614338
257 27889706845954689
258 28878022342605762
259 29897346562117382
260 30948527465259029
261 32032432810865865
262 33149950539543086
263 34301989163296458
264 35489478161157418
265 36713368380871645
266 37974632446720532
267 39274265173545518
268 40613283987045769
269 41992729350420229
270 43413665197425596
271 44877179371922314
272 46384384073981210
273 47936416312623945
274 49534438365270990
275 51179638243971382
276 52873230168489061
277 54616455046321137
278 56410580959723986
279 58256903659823626
280 60156747067887378
281 62111463783834373
282 64122435602063024
283 66191074034674142
284 68318820842168937
285 70507148571701709
286 72757561102967600
287 75071594201806346
288 77450816081603538
289 79896827972571473
290 82411264698992250
291 84995795264506342
292 87652123445530453
293 90381988392889049
294 93187165241744534
295 96069465729911626
296 99030738824642074
297 102072871357966445
298 105197788670680300
299 108407455265062670
300 111703875466415337
301 115089094093512021
302 118565197138047172
303 122134312453174666
304 125798610451227306
305 129560304810708633
306 133421653192649158
307 137384957966419734
308 141452566945095397
309 145626874130463617
310 149910320467771514
311 154305394610307210
312 158814633693911106
313 163440624121513493
314 168186002357795528
315 173053455734071230
316 178045723263488777
317 183165596466650013
318 188415920207747704
319 193799593541320714
320 199319570569727906
321 204978861311442209
322 210780532580266930
323 216727708875577030
324 222823573283688725
325 229071368390461417
326 235474397205236606
327 242036024096219082
328 248759675737406346
329 255648842067172861
330 262707077258616388
331 269938000701774318
332 277345297997818569
333 284932721965338277
334 292704093658820172
335 300663303399437194
336 308814311818256570
337 317161150911979241
338 325707925111323198
339 334458812362163958
340 343418065219546085
341 352590011954680337
342 361979057675041698
343 371589685457684234
344 381426457495889394
345 391494016259265061
346 401797085667413344
347 412340472277285790
348 423129066484345385
349 434167843737655405
350 445461865769015872
351 457016281836269066
352 468836329980896242
353 480927338300028401
354 493294726232994666
355 505944005862532518
356 518880783230784853
357 532110759670209529
358 545639733149527782
359 559473599634838602
360 573618354466026874
361 588080093748593805
362 602865015761038876
363 617979422377923278
364 633429720508745513
365 649222423552760565
366 665364152869874772
367 681861639267749258
368 698721724505245514
369 715951362812347449
370 733557622426694966
371 751547687146864854
372 769928857902535525
373 788708554341672865
374 807894316434875210
375 827493806097016202
376 847514808826325026
377 867965235361044277
378 888853123353806456
379 910186639063870846
380 931974079067363273
381 954223871985662013
382 976944580232073864
383 1000144901776945162
384 1023833671931353282
385 1048019865149524929
386 1072712596850128290
387 1097921125256586886
388 1123654853256563733
389 1149923330280765193
390 1176736254201214670
391 1204103473249147082
392 1232034987952675818
393 1260540953094384669
394 1289631679688998004
395 1319317636981283246
396 1349609454464340489
397 1380517923918434885
398 1412054001470528220
399 1444228809674666890
400 1477053639613384282
401 1510539953020276361
402 1544699384423910062
403 1579543743313224886
404 1615085016324588901
405 1651335369450671153
406 1688307150271293298
407 1726012890206424074
408 1764465306791481042
409 1803677305975104837
410 1843661984439571984
411 1884432631944013150
412 1926002733690604521
413 1968385972713900813
414 2011596232293479248
415 2055647598390064650
416 2100554362105306642
417 2146331022165380753
418 2192992287428586074
419 2240553079417112934
420 2289028534873154901
421 2338434008339540249
422 2388785074765058870
423 2440097532134661450
424 2492387404124708570
425 2545670942783448237
426 2599964631236901196
427 2655285186420334222
428 2711649561835502441
429 2769074950333842581
430 2827578786925799908
431 2887178751616472458
432 2947892772267757034
433 3009739027487182297
434 3072735949543615142
435 3136902227310027414
436 3202256809233510885
437 3268818906332729281
438 3336607995222997018
439 3405643821169175178
440 3475946401166576130
441 3547536027050069077
442 3620433268631579688
443 3694658976866177854
444 3770234287046948489
445 3847180622028841181
446 3925519695481695384
447 4005273515172638730
448 4086464386278056930
449 4169114914725334625
450 4253248010564567442
451 4338886891370446406
452 4426055085674516757
453 4514776436428014121
454 4605075104495481886
455 4696975572179374538
456 4790502646775852618
457 4885681464161975869
458 4982537492414502052
459 5081096535460499822
460 5181384736759984969
461 5283428583020790245
462 5387254907945879916
463 5492890896013321098
464 5600364086289124858
465 5709702376273170985
466 5820934025778431262
467 5934087660843706998
468 6049192277680097509
469 6166277246651417169
470 6285372316288779586
471 6406507617339568394
472 6529713666851015090
473 6655021372288605285
474 6782462035689535680
475 6912067357851445022
476 7043869442556643241
477 7177900800832063917
478 7314194355245166176
479 7452783444236013066
480 7593701826485754418
481 7736983685321743153
482 7882663633159514954
483 8030776715981862182
484 8181358417855233877
485 8334444665483694649
486 8490071832800676230
487 8648276745598756426
488 8809096686197701178
489 8972569398151006413
490 9138733090991177340
491 9307626445013983822
492 9479288616101931433
493 9653759240587188789
494 9831078440154212724
495 10011286826782313866
496 10194425507728406154
497 10380536090550184825
498 10569660688169978390
499 10761841923979521110
500 10957122936985893477
501 11155547386998879201
502 11357159459859988202
503 11562003872713396106
504 11770125879319051746
505 11981571275408205173
506 12196386404081609688
507 12414618161250652414
508 12636314001121668937
509 12861521941723698557
510 13090290570479937704
511 13322669049823150090
512 13558707122855293186
513 13798455119051621633
514 14041963960009529218
515 14289285165242392070
516 14540470858018676757
517 14795573771246577993
518 15054647253404451694
519 15317745274517310154
520 15584922432179647146
521 15856233957624861789
522 16131735721841551060
523 16411484241736941870
524 16695536686347734665
525 16983950883098631557
526 17276785324108823036
527 17574099172546708362
528 17875952269033125786
529 18182405138093369801
530 18493518994658273678
531 18809355750614636598
532 19129978021405275749
533 19455449132678984817
534 19785833126990681362
535 20121194770552026634
536 20461599560032802450
537 20807113729413330821
538 21157804256888223088
539 21513738871821746398
540 21874986061755096425
541 22241615079465866317
542 22613695950080002928
543 22991299478236542474
544 23374497255305418834
545 23763361666658638801
546 24157965898995119674
547 24558383947719485670
548 24964690624375120725
549 25376961564131776345
550 25795273233328034262
551 26219702937068924746
552 26650328826879002522
553 27087229908411183341
554 27530486049211645356
555 27980177986541100558
556 28436387335252742633
557 28899196595727178709
558 29368689161864653572
559 29844949329134876042
560 30328062302684758314
561 30818114205504380185
562 31315192086651491206
563 31819383929534864918
564 32330778660256820453
565 32849466156015227905
566 33375537253565315002
567 33909083757741593738
568 34450198450040226754
569 34998975097262154389
570 35555508460217304456
571 36119894302490207934
572 36692229399267344905
573 37272611546226546205
574 37861139568488777400
575 38457913329632632842
576 39063033740771868706
577 39676602769696305057
578 40298723450076428146
579 40929499890732025286
580 41569037284965185813
581 42217441919958002793
582 42874821186235311294
583 43541283587192800202
584 44216938748690835722
585 44901897428714335869
586 45596271527099036420
587 46300174095324489966
588 47013719346374140873
589 47737022664662820133
590 48470200616032005260
591 49213370957813191562
592 49966652648959722298
593 50730165860247426409
594 51504031984544413694
595 52288373647150378486
596 53083314716205764069
597 53888980313171141265
598 54705496823377155810
599 55532991906645400330
600 56371594507980567922
601 57221434868334245541
602 58082644535440706592
603 58955356374725063326
604 59839704580284140841
605 60735824685940435693
606 61643853576369523328
607 62563929498301279754
608 63496192071795284082
609 64440782301590769777
610 65397842588531493674
611 66367516741065893030
612 67349949986822902101
613 68345288984263800953
614 69353681834410470438
615 70375278092650428490
616 71410228780619024122
617 72458686398159166733
618 73520804935358969564
619 74596739884667687374
620 75686648253090329641
621 76790688574461331829
622 77909020921797668500
623 79041806919731793290
624 80189209757024792010
625 81351394199160136377
626 82528526601018427126
627 83720774919633516502
628 84928308727030401381
629 86151299223145279521
630 87389919248828162698
631 88644343298928441738
632 89914747535463799714
633 91201309800872870837
634 92504209631352043832
635 93823628270276809854
636 95159748681708056265
637 96512755563983708861
638 97882835363396126408
639 99270176287955652618
640 100674968321240731970
641 102097403236334997057
642 103537674609851736418
643 104995977836046153094
644 106472510141015825429
645 107967470596989782921
646 109481060136706611214
647 111013481567882001610
648 112564939587766161770
649 114135640797791505565
650 115725793718311041332
651 117335608803427879086
652 118965298455916278537
653 120615077042234661061
654 122285160907631010076
655 123975768391341085578
656 125687119841879879898
657 127419437632426743049
658 129172946176304607342
659 130947871942553742262
660 132744443471600471909
661 134562891391021288625
662 136403448431402797746
663 138266349442297929738
664 140151831408278857298
665 142060133465087056325
666 143991496915880950992
667 145946165247581584478
668 147924384147316758249
669 149926401518964084109
670 151952467499793394576
671 154002834477208958474
672 156077757105591949970
673 158177492323243620625
674 160302299369429625370
675 162452439801525954662
676 164628177512266926421
677 166829778747095692697
678 169057512121617717366
679 171311648639157682506
680 173592461708420282458
681 175900227161255365933
682 178235223270527887884
683 180597730768093134222
684 182988032862877683817
685 185406415259066573589
686 187853166174397133860
687 190328576358559962506
688 192832939111707507818
689 195366550303070731353
690 197929708389684323430
691 200522714435220945302
692 203145872128934973413
693 205799487804716222529
694 208483870460254125914
695 211199331776312852106
696 213946186136117839234
697 216724750644854229205
698 219535345149277685480
699 222378292257438079550
700 225253917358516532617
701 228162548642776300381
702 231104517121627990232
703 234080156647809601546
704 237089803935681881186
705 240133798581639487713
706 243212483084638459218
707 246326202866840481094
708 249475306294374451477
709 252660144698215843497
710 255881072395184364894
711 259138446709060416970
712 262432627991820856266
713 265763979644994563773
714 269132868141138327908
715 272539663045433548910
716 275984737037404273737
717 279468465932757071973
718 282991228705343264684
719 286553407509244019594
720 290155387700978827386
721 293797557861837875369
722 297480309820338836190
723 301204038674808590710
724 304969142816090405605
725 308776023950377087697
726 312625087122170638466
727 316516740737368933642
728 320451396586479954226
729 324429469867964096741
730 328451379211705091968
731 332517546702610062878
732 336628397904339253929
733 340784361883165965357
734 344985871231967227552
735 349233362094345752074
736 353527274188883697330
737 357868050833528788401
738 362256138970113331978
739 366691989189006668838
740 371176055753901607765
741 375708796626735386297
742 380290673492745705158
743 384922151785662384714
744 389603700713035193274
745 394335793281698398541
746 399118906323372595004
747 403953520520404361550
748 408840120431644305065
749 413779194518464047285
750 418771235170912713652
751 423816738734013484426
752 428916205534200769802
753 434070139905898572281
754 439279050218240601046
755 444543448901932704598
756 449863852476258189413
757 455240781576226593889
758 460674760979866488362
759 466166319635662873482
760 471715990690139750754
761 477324311515588440565
762 482991823737942224536
763 488719073264797890558
764 494506610313584760393
765 500354989439881781245
766 506264769565883264232
767 512236514009013854218
768 518270790510693316994
769 524368171265251731329
770 530529232948995674946
771 536754556749425995014
772 543044728394607755285
773 549400338182692953545
774 555821981011596604590
775 562310256408826785482
776 568865768561469241386
777 575489126346327151837
778 582180943360216658836
779 588941837950418759726
780 595772433245288169353
781 602673357185019757573
782 609645242552573169724
783 616688727004756239242
784 623804453103467803162
785 630993068347100532809
786 638255225202104393550
787 645591581134711349046
788 653002798642821927013
789 660489545288054265073
790 668052493727956256850
791 675692321748381420042
792 683409712296029109778
793 691205353511149702149
794 699079938760415374384
795 707034166669957109726
796 715068741158568556649
797 723184371471077373645
798 731381772211884692400
799 739661663378673333770
800 748024770396285412562
801 756471824150769968721
802 765003561023601264122
803 773620722926068385766
804 782324057333836797781
805 791114317321682486233
806 799992261598399342358
807 808958654541880431434
808 818014266234373796122
809 827159872497913444717
810 836396254929926176364
811 845724200939014896910
812 855144503780919080681
813 864657962594653035093
814 874265382438822626628
815 883967574328121128330
816 893765355270004850602
817 903659548301549218713
818 913650982526485962054
819 923740493152422081814
820 933928921528241265381
821 944217115181688417409
822 954605927857137979130
823 965096219553546709130
824 975688856562591600450
825 986384711506993610517
826 997184663379027882056
827 1008089597579221134782
828 1019100405955236909321
829 1030217986840949346461
830 1041443245095706186488
831 1052777092143781675018
832 1064220446014020063394
833 1075774231379670393377
834 1087439379598413257522
835 1099216828752580228294
836 1111107523689566650645
837 1123112416062438494441
838 1135232464370733964798
839 1147468634001460570058
840 1159821897270288348810
841 1172293233462939959037
842 1184883628876778334148
843 1197594076862592612334
844 1210425577866583047369
845 1223379139472545610661
846 1236455776444256996044
847 1249656510768060740490
848 1262982371695655175610
849 1276434395787083926505
850 1290013626953929676222
851 1303721116502711915766
852 1317557923178489401317
853 1331525113208668042001
854 1345623760347014943266
855 1359854945917879332618
856 1374219758860621096178
857 1388719295774247656229
858 1403354660962259921632
859 1418126966477708044702
860 1433037332168457719849
861 1448086885722667761005
862 1463276762714479696576
863 1478608106649920122378
864 1494082069013016554738
865 1509699809312127527665
866 1525462495126487679722
867 1541371302152968577958
868 1557427414253056027989
869 1573632023500044621049
870 1589986330226450270566
871 1606491543071641492554
872 1623148879029690185850
873 1639959563497442669965
874 1656924830322811740060
875 1674045921853290500302
876 1691324088984688738601
877 1708760591210092607477
878 1726356696669048377556
879 1744113682196971031946
880 1762032833374778471498
881 1780115444578752102713
882 1798362819030624581814
883 1816776268847895490262
884 1835357115094375718757
885 1854106687830961338529
886 1873026326166637740490
887 1892117378309714824586
888 1911381201619294023458
889 1930819162656967946293
890 1950432637238753430520
891 1970223010487258790782
892 1990191676884086056393
893 2010340040322468990269
894 2030669514160147684104
895 2051181521272480526346
896 2071877494105794341314
897 2092758874730973499585
898 2113827114897288801570
899 2135083676086466937990
900 2156530029567001332757
901 2178167656448705175561
902 2199998047737507453262
903 2222022704390492790986
904 2244243137371185915626
905 2266660867705081556253
906 2289277426535420597748
907 2312094355179213305774
908 2335113205183510443017
909 2358335538381923098437
910 2381762926951392053084
911 2405396953469207507850
912 2429239210970280000346
913 2453291303004663339913
914 2477554843695330391598
915 2502031457796202541750
916 2526722780750433679717
917 2551630458748949531953
918 2576756148789243186674
919 2602101518734427649034
920 2627668247372546268626
921 2653458024476141882949
922 2679472550862085522320
923 2705713538451665523550
924 2732182710330937901545
925 2758881800811338829837
926 2785812555490560082896
927 2812976731313688294922
928 2840376096634608891666
929 2868012431277675553681
930 2895887526599646071258
931 2924003185551885453158
932 2952361222742837153109
933 2980963464500763279897
934 3009811748936754658742
935 3038907926008011613514
936 3068253857581396341210
937 3097851417497257751981
938 3127702491633529649868
939 3157808977970103131278
940 3188172786653474080105
941 3218795840061666640277
942 3249680072869433548388
943 3280827432113734210954
944 3312239877259491412714
945 3343919380265627544281
946 3375867925651381239334
947 3408087510562905313430
948 3440580144840146898405
949 3473347851084010668225
950 3506392664723806054042
951 3539716634084979348106
952 3573321820457131598082
953 3607210298162323195221
954 3641384154623666061736
955 3675845490434204344638
956 3710596419426084525193
957 3745639068740015855069
958 3780975578895022032152
959 3816608103858485030922
960 3852538811116482004194
961 3888769881744416174945
962 3925303510477942638866
963 3962141905784190000198
964 3999287289933278765333
965 4036741899070137420585
966 4074507983286617122462
967 4112587806693905930698
968 4150983647495243516234
969 4189697798058937278269
970 4228732564991680806436
971 4268090269212175626094
972 4307773246025057166665
973 4347783845195125894885
974 4388124431021884556780
975 4428797382414382474122
976 4469805092966367843066
977 4511149971031748984617
978 4552834439800365498526
979 4594860937374070274166
980 4637231916843123313893
981 4679949846362898326353
982 4723017209230903049154
983 4766436503964114262282
984 4810210244376628455602
985 4854340959657629115749
986 4898831194449671599680
987 4943683508927286564126
988 4988900478875902922153
989 5034484695771091300013
990 5080438766858128969440
991 5126765315231887232522
992 5173466979917042238258
993 5220546415948610211889
994 5268006294452808080074
995 5315849302728240476966
996 5364078144327414118229
997 5412695539138580532025
998 5461704223467908137990
999 5511106950121984667210
1000 5560906488490650918202