0 1
1 1
2 1
3 1
4 2
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 15
13 19
14 24
15 30
16 39
17 48
18 60
19 75
20 93
21 115
22 142
23 173
24 213
25 260
26 316
27 383
28 465
29 560
30 676
31 812
32 974
33 1165
34 1393
35 1658
36 1975
37 2345
38 2779
39 3288
40 3887
41 4582
42 5398
43 6346
44 7452
45 8735
46 10230
47 11956
48 13964
49 16283
50 18964
51 22057
52 25632
53 29739
54 34477
55 39917
56 46171
57 53342
58 61572
59 70985
60 81773
61 94097
62 108181
63 124250
64 142592
65 163473
66 187269
67 214329
68 245104
69 280055
70 319750
71 364753
72 415797
73 473597
74 539042
75 613060
76 696767
77 791298
78 898064
79 1018504
80 1154338
81 1307391
82 1479805
83 1673825
84 1892141
85 2137552
86 2413343
87 2723033
88 3070691
89 3460636
90 3897918
91 4387900
92 4936755
93 5551143
94 6238668
95 7007491
96 7866997
97 8827239
98 9899658
99 11096666
100 12432288
101 13921671
102 15582017
103 17431896
104 19492241
105 21785807
106 24338130
107 27176913
108 30333318
109 33841122
110 37738123
111 42065508
112 46869206
113 52199158
114 58111151
115 64665818
116 71930631
117 79979150
118 88893023
119 98761172
120 109682356
121 121764069
122 135125371
123 149896139
124 166219942
125 184253206
126 204168917
127 226155488
128 250420823
129 277191661
130 306717807
131 339271500
132 375152679
133 414688056
134 458237012
135 506191334
136 558981445
137 617076245
138 680990805
139 751286045
140 828577295
141 913534936
142 1006893645
143 1109453378
144 1222090596
145 1345759226
146 1481503333
147 1630459526
148 1793870730
149 1973089326
150 2169593733
151 2384991977
152 2621040398
153 2879649341
154 3162903847
155 3473070735
156 3812623255
157 4184249238
158 4590879117
159 5035697374
160 5522173671
161 6054076802
162 6635511597
163 7270935172
164 7965198928
165 8723569770
166 9551777298
167 10456039341
168 11443117454
169 12520346704
170 13695699071
171 14977821003
172 16376104932
173 17900733965
174 19562765767
175 21374184713
176 23347997837
177 25498298885
178 27840377171
179 30390793411
180 33167506686
181 36189962848
182 39479240096
183 43058155799
184 46951432125
185 51185821655
186 55790300192
187 60796213045
188 66237496105
189 72150850482
190 78575994761
191 85555869621
192 93136930465
193 101369385192
194 110307530151
195 120010031488
196 130540309023
197 141966864510
198 154363726128
199 167810829383
200 182394527177
201 198208037440
202 215352026749
203 233935131022
204 254074629718
205 275897048712
206 299538934204
207 325147557447
208 352881800481
209 382912973504
210 415425836370
211 450619543461
212 488708815500
213 529925039072
214 574517608320
215 622755197016
216 674927303141
217 731345716580
218 792346290263
219 858290642121
220 929568182246
221 1006598077440
222 1089831581571
223 1179754298420
224 1276888851766
225 1381797501039
226 1495085196655
227 1617402593078
228 1749449555622
229 1891978625167
230 2045799033195
231 2211780696377
232 2390858807851
233 2584038429745
234 2792399756050
235 3017103385171
236 3259396339941
237 3520618132073
238 3802207641742
239 4105710077730
240 4432784852302
241 4785213559636
242 5164908975508
243 5573924215132
244 6014463009240
245 6488890196738
246 6999743473076
247 7549745400431
248 8141816820442
249 8779090613777
250 9464927002127
251 10202929289194
252 10996961332836
253 11851165536860
254 12769982778979
255 13758172987895
256 14820837856890
257 15963444349121
258 17191850601898
259 18512332756895
260 19931614474399
261 21456897570067
262 23095895623216
263 24856868924725
264 26748662761239
265 28780747253878
266 30963260933659
267 33307056165264
268 35823748717870
269 38525769511768
270 41426421022297
271 44539936194367
272 47881542575035
273 51467529393764
274 55315320447754
275 59443550422530
276 63872147731706
277 68622421303338
278 73717154675004
279 79180704679936
280 85039108277370
281 91320194695629
282 98053706722424
283 105271428076588
284 113007321037442
285 121297671100175
286 130181243079742
287 139699445299134
288 149896506634458
289 160819662787416
290 172519356979471
291 185049451249821
292 198467453865660
293 212834758880258
294 228216903785249
295 244683840991913
296 262310229610382
297 281175743052972
298 301365399335457
299 322969909441020
300 346086051167836
301 370817063494713
302 397273069535166
303 425571522887244
304 455837685969453
305 488205134982097
306 522816300774381
307 559823039895644
308 599387245921251
309 641681495096594
310 686889737060478
311 735208024524497
312 786845293538824
313 842024187843667
314 900981939953825
315 963971302241295
316 1031261541530069
317 1103139490321394
318 1179910669267366
319 1261900473629046
320 1349455439616226
321 1442944583138870
322 1542760827990582
323 1649322515890702
324 1763075016809901
325 1884492431649536
326 2014079407321742
327 2152373056149130
328 2299945001090186
329 2457403538693809
330 2625395943086363
331 2804610902602881
332 2995781114426850
333 3199686028811690
334 3417154770151918
335 3649069226602958
336 3896367337827427
337 4160046572406032
338 4441167627129132
339 4740858339850761
340 5060317850607482
341 5400821003046700
342 5763723023848917
343 6150464472248796
344 6562576500728729
345 7001686419431255
346 7469523608627902
347 7967925772508095
348 8498845582491574
349 9064357703752532
350 9666666257537170
351 10308112713856298
352 10991184271424040
353 11718522720685800
354 12492933851842873
355 13317397404694320
356 14195077627884425
357 15129334445952460
358 16123735307433321
359 17182067714459643
360 18308352513694912
361 19506857950869405
362 20782114576152897
363 22138931005208101
364 23582410630641283
365 25117969291907137
366 26751354007024365
367 28488662777206864
368 30336365577455508
369 32301326548239100
370 34390827511228232
371 36612592829079744
372 38974815743606215
373 41486186217167558
374 44155920424347708
375 46993791924840746
376 50010164677783409
377 53216027935687569
378 56623033193229675
379 60243533236439132
380 64090623484312675
381 68178185677424564
382 72520934123090807
383 77134464562203506
384 82035305887178292
385 87240974787140952
386 92770033571966540
387 98642151264440468
388 104878168235518262
389 111500164487155403
390 118531531884074274
391 125997050455026357
392 133922969094286748
393 142337090802847948
394 151268862831233259
395 160749471885059074
396 170811944790354839
397 181491254802948567
398 192824433997929863
399 204850691950394674
400 217611541185136921
401 231150929637117242
402 245515380647102684
403 260754140767308747
404 276919335953312874
405 294066136455016067
406 312252931038619546
407 331541510895346108
408 351997263931177589
409 373689379839908096
410 396691066722883234
411 421079779710852168
412 446937462425805045
413 474350801798116773
414 503411497160027816
415 534216544195968971
416 566868534762894639
417 601475973235069558
418 638153610486180349
419 677022796246252758
420 718211851057297918
421 761856458655850570
422 808100080129267786
423 857094390776279594
424 908999741152103654
425 963985643343208906
426 1022231284100422691
427 1083926066000876798
428 1149270178431622481
429 1218475199706389701
430 1291764732286918630
431 1369375072577791871
432 1451555917464472131
433 1538571109236108584
434 1630699421282009392
435 1728235386396730064
436 1831490170321652657
437 1940792492573548096
438 2056489597452963490
439 2178948277519519457
440 2308555952719671537
441 2445721807718345701
442 2590877990939665826
443 2744480878162208084
444 2907012404528003017
445 3078981468133766391
446 3260925409454437065
447 3453411570127524158
448 3657038935775724070
449 3872439866796170754
450 4100281922266588328
451 4341269781336266277
452 4596147267773847787
453 4865699482528756335
454 5150755050549329323
455 5452188487256672842
456 5770922691548481607
457 6107931571328105124
458 6464242809129218719
459 6840940774493393104
460 7239169591433465233
461 7660136368373280140
462 8105114599738800821
463 8575447747397681889
464 9072553012050552673
465 9597925303665223921
466 10153141422074516477
467 10739864457818126987
468 11359848425471936105
469 12014943140633303627
470 12707099354042730471
471 13438374155215073440
472 14210936660417092744
473 15027073998695941852
474 15889197612291064807
475 16799849886598564833
476 17761711127667621591
477 18777606904017388904
478 19850515772560621550
479 20983577407210553950
480 22180101151948132690
481 23443575018892675564
482 24777675155344473861
483 26186275802514604781
484 27673459772314568488
485 29243529467317531374
486 30901018472911376475
487 32650703749390470511
488 34497618455919305203
489 36447065437022857718
490 38504631406732754840
491 40676201864249745082
492 42967976779769109069
493 45386487087853539516
494 47938612030868545846
495 50631597393750285639
496 53473074676865053342
497 56471081252510420895
498 59634081556486001960
499 62970989364987612981
500 66491191213384970478
501 70204571012318676039
502 74121535923306934009
503 78253043555002202649
504 82610630548478490277
505 87206442618956719137
506 92053266129150695652
507 97164561268540261507
508 102554496921215229384
509 108237987304186627678
510 114230730467007859506
511 120549248742938167182
512 127210931251496155238
513 134234078551805856062
514 141637949556459402082
515 149442810815380842316
516 157669988290263008959
517 166341921740131017617
518 175482221850513767624
519 185115730238945865105
520 195268582482340191535
521 205968274312324923886
522 217243731138421991931
523 229125381059835704246
524 241645231541461800011
525 254836949931008881880
526 268735948010090176571
527 283379470773884269817
528 298806689651149601516
529 315058800378617052350
530 332179125762307382152
531 350213223561128298290
532 369208999748052381310
533 389216827407643685343
534 410289671550192955322
535 432483220126905396144
536 455856021553768506390
537 480469629056722297691
538 506388752175745044409
539 533681415771390679326
540 562419126904267054279
541 592677049964880138210
542 624534190460368033622
543 658073587872721896572
544 693382518034487767342
545 730552705477307014826
546 769680546242545958586
547 810867341654038423905
548 854219543589585399017
549 899849011800204230800
550 947873283865667556860
551 998415858388995049824
552 1051606492075289010895
553 1107581511356367265586
554 1166484139268848085554
555 1228464838311562895403
556 1293681670058108517995
557 1362300672320990581117
558 1434496254717803856049
559 1510451613513179382429
560 1590359166668652393965
561 1674421010058822789055
562 1762849395875375106761
563 1855867234270015114451
564 1953708619355760637136
565 2056619380719092190465
566 2164857661669507401700
567 2278694525490049722777
568 2398414591032522463484
569 2524316699042525463298
570 2656714610686225081357
571 2795937739797004328979
572 2942331920454147862259
573 3096260211557262754430
574 3258103740161955766997
575 3428262585399717644183
576 3607156704915277239653
577 3795226905818549223515
578 3992935862267870836790
579 4200769181872170242098
580 4419236523229289536716
581 4648872766996464237031
582 4890239243029423158792
583 5143925016213909545964
584 5410548233765746885406
585 5690757536872324254798
586 5985233539713530140510
587 6294690379007297057541
588 6619877337404024677317
589 6961580544172624654350
590 7320624756815237151997
591 7697875227378603314506
592 8094239657440842890306
593 8510670245897034124529
594 8948165833895652734258
595 9407774151437551346102
596 9890594170397313156423
597 10397778568902868771373
598 10930536312278534439061
599 11490135355950741093710
600 12077905476007952890697
601 12695241233320097430097
602 13343605077440062269562
603 14024530596745237326717
604 14739625921621415227001
605 15490577287750491686601
606 16279152766937204784354
607 17107206173195151651139
608 17976681152218195586365
609 18889615462676697143718
610 19848145458218658771367
611 20854510779400232843894
612 21911059265248512758570
613 23020252094537748615628
614 24184669167379755734244
615 25407014738144542296818
616 26690123311291449168730
617 28036965812146900192339
618 29450656045277655540484
619 30934457453608482070224
620 32491790192098753241309
621 34126238530340834794661
622 35841558599165997385183
623 37641686496944791581357
624 39530746772053974532122
625 41513061298640882643971
626 43593158563669037954996
627 45775783383950494326350
628 48065907072796824461387
629 50468738076711115587514
630 52989733103549620848850
631 55634608764447091559911
632 58409353752892975416444
633 61320241585292794271552
634 64373843928536456106630
635 67577044541131644484182
636 70937053855750323938459
637 74461424232170013370437
638 78158065910992773855609
639 82035263699764504339776
640 86101694424639327986953
641 90366445182089188573512
642 94839032426812320082098
643 99529421933475553725008
644 104448049671721757600587
645 109605843635492301347093
646 115014246669665729536932
647 120685240338782122705267
648 126631369884742255149629
649 132865770322301886652656
650 139402193723484100109813
651 146255037744141316871979
652 153439375448399732912617
653 160970986489021043947544
654 168866389704433076747812
655 177142877195693494905697
656 185818549949601785346048
657 194912355076916393563923
658 204444124737839155275301
659 214434616829920341894340
660 224905557517019005427145
661 235879685681215846500492
662 247380799383357089952714
663 259433804421465710271836
664 272064765080363014149737
665 285300957169722885053342
666 299170923452240954540068
667 313704531567829739709992
668 328933034564594405179824
669 344889134151952730055165
670 361607046796522729570291
671 379122572786423864993620
672 397473168395349477579409
673 416698021283240043788665
674 436838129276589093447887
675 457936382677374302667411
676 480037650256340660419568
677 503188869092854692599405
678 527439138430860621934059
679 552839817727538793100688
680 579444629079205412018421
681 607309764216689596891966
682 636493996271042338476392
683 667058796518810941604416
684 699068456325468796366885
685 732590214514710052947438
686 767694390401475519441376
687 804454522736500573176548
688 842947514821200699418224
689 883253786062509048381658
690 925457430249246883791623
691 969646380843355844770184
692 1015912583592308981029693
693 1064352176781796454385447
694 1115065679461877477903400
695 1168158187993688534379555
696 1223739581279094844347244
697 1281924735050785659285815
698 1342833745616913725687341
699 1406592163470811987045021
700 1473331237194332722062067
701 1543188168101219040735205
702 1616306376086462156447742
703 1692835777167016359081201
704 1772933073220447564158949
705 1856762054449195960530701
706 1944493915121136905700420
707 2036307583160058619450186
708 2132390064184629706435055
709 2232936800619348679373607
710 2338152046528036900236977
711 2448249258847508558498107
712 2563451505728412159148661
713 2683991892719645802702191
714 2810114007564592906895568
715 2942072384409365487127758
716 3080132988257777979146895
717 3224573720542461580581257
718 3375684946718980901498647
719 3533770046827480066620670
720 3699145990006996602026402
721 3872143933988475450434837
722 4053109850636549745550667
723 4242405178654549144029382
724 4440407504614938544086316
725 4647511273525578523786214
726 4864128530193957164725793
727 5090689692703843412854328
728 5327644359374920914354446
729 5575462150632718095039167
730 5834633587276970204145121
731 6105671006698135194351243
732 6389109518657707252951102
733 6685508002314790027542263
734 6995450146252838611941943
735 7319545533332966072835774
736 7658430772277639152894886
737 8012770677967215477935056
738 8383259502515679943044377
739 8770622219277216847160913
740 9175615862026171498059640
741 9599030921645437707626298
742 10041692802756814478058585
743 10504463342827159747814359
744 10988242396390891298179785
745 11493969487138117181928786
746 12022625530733292436029656
747 12575234631347177943665815
748 13152865955010114564782749
749 13756635683022408013380550
750 14387709048793270747401069
751 15047302461618269520340378
752 15736685721052146677520453
753 16457184325683989540819487
754 17210181880280833437684865
755 17997122605428449989647799
756 18819513953970373824009078
757 19678929338722478850092512
758 20577010976126986727092964
759 21515472850700756505158322
760 22496103805334711242967349
761 23520770762708139244792477
762 24591422083300309891541403
763 25710091065705944561963347
764 26878899595197843031406226
765 28100061946722694114571392
766 29375888748772386929191859
767 30708791114836018511532715
768 32101284949415198030520774
769 33555995435869922346483299
770 35075661713662536250458103
771 36663141752875537621947629
772 38321417434203913669081358
773 40053599842956434111493194
774 41862934785951943088997907
775 43752808540557996805791778
776 45726753845499663181757087
777 47788456143457410315684123
778 49941760085884667665607912
779 52190676310898979147485161
780 54539388505546034208443105
781 56992260764194033998676371
782 59553845255297649897090404
783 62228890209266659016027203
784 65022348240695513304347400
785 67939385018746628488645442
786 70985388300043896505864082
787 74165977339013443525658336
788 77487012691218344844471269
789 80954606425862064433890106
790 84575132764294744231162101
791 88355239162035894649343587
792 92301857852540053980992070
793 96422217871666914500521813
794 100723857582588395701782579
795 105214637721660041887503694
796 109902754986617716627994565
797 114796756189320247015181426
798 119905552996159893523875278
799 125238437280192181057375103
800 130805097110010888838838538
801 136615633401399243652897268
802 142680577258841498345979901
803 149010908035065962451750102
804 155618072137928862055180009
805 162514002615123454714024911
806 169711139548429102334645357
807 177222451290485258489314244
808 185061456578404896215027812
809 193242247559914956648511818
810 201779513769148163608356303
811 210688567090694594332129430
812 219985367752073880193893261
813 229686551386392781797317102
814 239809457208630274312348297
815 250372157350725503266997078
816 261393487402456180661924054
817 272893078206967841128022243
818 284891388961772092112422635
819 297409741678055544764411824
820 310470357053255849505036996
821 324096391814047459863766721
822 338311977589163928044454147
823 353142261373845255687164941
824 368613447650165834687914335
825 384752842230049632956777746
826 401588897890443551537519725
827 419151261872875361564301521
828 437470825322499714783098164
829 456579774744711688549388904
830 476511645560513988888516133
831 497301377845037766382428111
832 518985374336971301718246137
833 541601560810121242636161352
834 565189448901952480979256658
835 589790201497699956342997389
836 615446700772555159875449947
837 642203618998475828028664495
838 670107492226387478410315958
839 699206796958913104972151469
840 729552029933322532658108391
841 761195791139107784103550780
842 794192870199507241847225844
843 828600336251390620539301543
844 864477631463222690050913353
845 901886668336316591156003530
846 940891930940313435752520083
847 981560580239752999382851668
848 1023962563674778861468510799
849 1068170729165418657391447589
850 1114260943715546642394579412
851 1162312216799538862682266113
852 1212406828721823759780119846
853 1264630464146979318200911001
854 1319072351005787318806991579
855 1375825404990691163413956499
856 1434986379862474171880895233
857 1496656023798644462258594926
858 1560939242023041385436109826
859 1627945265965530184208619145
860 1697787829210389908472148845
861 1770585350502086757432694507
862 1846461124087627859468064919
863 1925543517685570082988297048
864 2007966178383084970769633198
865 2093868246774214268794737948
866 2183394579664664379925461421
867 2276695981681141285741430280
868 2373929446136397252136176424
869 2475258405514804757407389750
870 2580852991957472546018930999
871 2690890308140630228068058492
872 2805554708956316397483354756
873 2925038094420266460081869560
874 3049540214248399431070525567
875 3179268984560402447390330532
876 3314440817186701244186188891
877 3455280962073537884227153420
878 3602023863300051865726839982
879 3754913529241129846773910267
880 3914203917430455781892427016
881 4080159334699608744173918905
882 4253054853191328434195701894
883 4433176742868148856067062568
884 4620822921161602650688847896
885 4816303420432071671445822336
886 5019940873935223089216548946
887 5232071021017773285681974391
888 5453043232293189601177540922
889 5683221055576820468347503595
890 5922982783389969535715184264
891 6172722042873546097674538524
892 6432848408984271181330339926
893 6703788041879942319274490061
894 6985984349435106133905280689
895 7279898675864602065333077945
896 7586011017469976160281307773
897 7904820766562665944750302261
898 8236847484658287205696563445
899 8582631706078255713462346777
900 8942735773138521040865931076
901 9317744704150320062897076056
902 9708267095504752783458209785
903 10114936059161587016892737744
904 10538410196913198790928440383
905 10979374612846896277696912429
906 11438541965483254059429128266
907 11916653561124445858210705519
908 12414480490005115354757599994
909 12932824806899010940743298627
910 13472520757897650020355597104
911 14034436055142616856562367883
912 14619473201360965363599085144
913 15228570866123540462400991369
914 15862705315819091328199940640
915 16522891899412773811116382788
916 17210186592136283161189733911
917 17925687599338369929176207269
918 18670537022809140909008725957
919 19445922591979282772037199380
920 20253079462486452500278428901
921 21093292084695507250354668649
922 21967896144857296112439318510
923 22878280581692361003958580483
924 23825889681291409134940712898
925 24812225253333781368509341260
926 25838848891738682064312680232
927 26907384322981615954038142715
928 28019519845430647161371563011
929 29177010863183717510399309102
930 30381682518019705945732278501
931 31635432423212145143530089020
932 32940233503095925841950166925
933 34298136942423885603166635141
934 35711275249702308901183941575
935 37181865438852036402913086617
936 38712212333705528258573553453
937 40304712000019831854952778511
938 41961855309861428310779677199
939 43686231643401363356054203848
940 45480532733348392406053262951
941 47347556657444083420616096191
942 49290211984647437102451360445
943 51311522080847607257217660185
944 53414629580162276263964012116
945 55602801028106175948641533459
946 57879431703149714997175777712
947 60248050623431705035567101066
948 62712325745643373502524314302
949 65276069363363248481829979707
950 67943243712394738201004585330
951 70717966790940354544940251946
952 73604518402739221837696717253
953 76607346431597831815348301538
954 79731073356058668243412293223
955 82980503013277407828245068283
956 86360627621517664392052336454
957 89876635071022775333361168794
958 93533916493387733549300989060
959 97338074119931157343693141433
960 101294929439958012361605014652
961 105410531670208786629072443047
962 109691166547210868843748205865
963 114143365454683146675079840637
964 118773914898596275107652948797
965 123589866342958844595305740247
966 128598546419884809969032320551
967 133807567528000229978455457236
968 139224838833768678424765002619
969 144858577690854856306453643485
970 150717321493206087744723607067
971 156809939978111787506414104468
972 163145647996102839253193773070
973 169734018765176422438815881164
974 176584997627478437929089597619
975 183708916327245646571171131656
976 191116507829504292789684985359
977 198818921699741716216422919284
978 206827740065513680661043205397
979 215154994181723295054525562123
980 223813181622108973387871126946
981 232815284120309351832496825336
982 242174786084734050404216045099
983 251905693812361157628949929943
984 262022555427507025898549316374
985 272540481572571973095036425534
986 283475166878758592037164932826
987 294842912245788215231544855104
988 306660647960707577526336027821
989 318945957686982571942562873338
990 331717103356221230244166735055
991 344993050996054460084558108497
992 358793497528932785246520435644
993 373138898577871222851497472442
994 388050497316494774222345978685
995 403550354402104746933198779509
996 419661379031903688089659539213
997 436407361163985126799856398515
998 453813004946216170735868829566
999 471903963397717409869912821822
1000 490706874389278283199666978764