0 1
1 1
2 1
3 1
4 2
5 3
6 3
7 4
8 7
9 8
10 10
11 14
12 18
13 22
14 29
15 37
16 47
17 58
18 73
19 91
20 113
21 140
22 174
23 211
24 260
25 319
26 386
27 468
28 572
29 687
30 828
31 998
32 1197
33 1431
34 1714
35 2041
36 2430
37 2887
38 3424
39 4051
40 4792
41 5651
42 6659
43 7829
44 9199
45 10786
46 12631
47 14770
48 17258
49 20120
50 23444
51 27278
52 31697
53 36788
54 42664
55 49394
56 57150
57 66045
58 76236
59 87911
60 101301
61 116570
62 134045
63 153991
64 176737
65 202651
66 232196
67 265770
68 303982
69 347382
70 396661
71 452552
72 515957
73 587738
74 669047
75 761008
76 865008
77 982483
78 1115170
79 1264852
80 1433713
81 1623962
82 1838310
83 2079559
84 2351013
85 2656188
86 2999206
87 3384359
88 3816805
89 4301905
90 4845883
91 5455493
92 6138453
93 6902911
94 7758498
95 8715357
96 9785065
97 10980266
98 12315259
99 13805305
100 15468098
101 17322471
102 19389727
103 21693165
104 24258921
105 27115106
106 30293823
107 33829556
108 37760999
109 42130422
110 46985028
111 52375882
112 58360561
113 65001261
114 72367420
115 80534811
116 89587657
117 99617410
118 110726240
119 123024946
120 136636652
121 151695542
122 168350249
123 186762540
124 207111847
125 229593158
126 254422366
127 281834587
128 312089332
129 345469336
130 382286657
131 422880752
132 467626180
133 516930591
134 571242604
135 631051142
136 696893731
137 769355246
138 849079122
139 936765315
140 1033182029
141 1139166192
142 1255635293
143 1383587480
144 1524117781
145 1678416820
146 1847788257
147 2033651482
148 2237558784
149 2461198104
150 2706416725
151 2975222133
152 3269807744
153 3592559577
154 3946081974
155 4333205077
156 4757019292
157 5220880934
158 5728450397
159 6283705632
160 6890981032
161 7554983202
162 8280841536
163 9074122871
164 9940888137
165 10887717372
166 11921769142
167 13050810397
168 14283290818
169 15628373505
170 17096019709
171 18697032878
172 20443149496
173 22347092361
174 24422680885
175 26684888901
176 29149971551
177 31835540641
178 34760703759
179 37946155735
180 41414343004
181 45189566048
182 49298170449
183 53768672777
184 58631973013
185 63921507551
186 69673495758
187 75927114233
188 82724784691
189 90112380961
190 98139553006
191 106859977518
192 116331729070
193 126617568261
194 137785376507
195 149908491570
196 163066200190
197 177344142173
198 192834871035
199 209638320518
200 227862461022
201 247623837127
202 269048315376
203 292271727102
204 317440716069
205 344713482008
206 374260771696
207 406266730966
208 440930036547
209 478464907686
210 519102388515
211 563091517992
212 610700824268
213 662219662462
214 717959924549
215 778257616287
216 843474794815
217 914001391204
218 990257460828
219 1072695265610
220 1161801850568
221 1258101482176
222 1362158571733
223 1474580490004
224 1596020949267
225 1727183219062
226 1868823999919
227 2021757166741
228 2186858168474
229 2365068343252
230 2557399991234
231 2764941304892
232 2988862177583
233 3230419913902
234 3490965834242
235 3771951847282
236 4074938040001
237 4401600187367
238 4753738439879
239 5133285983852
240 5542318925672
241 5983066244360
242 6457921120074
243 6969452303119
244 7520417070684
245 8113774291647
246 8752699174084
247 9440598255724
248 10181126265736
249 10978203241240
250 11836033797065
251 12759126737511
252 13752316989137
253 14820788068001
254 15970097108257
255 17206200499102
256 18535482458265
257 19964784336028
258 21501437130563
259 23153295005690
260 24928772333180
261 26836881908557
262 28887277195583
263 31090295920815
264 33457008122134
265 35999265935719
266 38729758258164
267 41662067458729
268 44810731646292
269 48191309255251
270 51820449823905
271 55715967643046
272 59896922176903
273 64383701872038
274 69198115661456
275 74363488270645
276 79904764149667
277 85848615994523
278 92223562711709
279 99060092780025
280 106390798313588
281 114250515167888
282 122676475085442
283 131708465004423
284 141388999573016
285 151763502049699
286 162880500133420
287 174791831179743
288 187552864245961
289 201222733119296
290 215864587855626
291 231545859104722
292 248338543316281
293 266319502273389
294 285570786182979
295 306179973364765
296 328240535926883
297 351852224665782
298 377121483224788
299 404161883818753
300 433094595967190
301 464048880025405
302 497162617237744
303 532582868366044
304 570466473367314
305 610980683170805
306 654303837744023
307 700626080847594
308 750150126143674
309 803092065393991
310 859682234294696
311 920166125635458
312 984805367400102
313 1053878754708748
314 1127683353977008
315 1206535668592208
316 1290772885540375
317 1380754191250848
318 1476862178567454
319 1579504332173681
320 1689114615545199
321 1806155147229362
322 1931117990815463
323 2064527045441715
324 2206940064154507
325 2358950785886491
326 2521191210088784
327 2694334000329095
328 2879095047496944
329 3076236178162164
330 3286568042243923
331 3510953164324274
332 3750309195237439
333 4005612348918227
334 4277901063172493
335 4568279868897369
336 4877923510618167
337 5208081301578749
338 5560081759720851
339 5935337508577198
340 6335350492034309
341 6761717487025255
342 7216135968164154
343 7700410307080451
344 8216458365238193
345 8766318464018180
346 9352156794273836
347 9976275249877551
348 10641119753607011
349 11349289058722053
350 12103544101041688
351 12906817886241762
352 13762225991728118
353 14673077669550934
354 15642887637244913
355 16675388542231934
356 17774544195306052
357 18944563560782026
358 20189915604912639
359 21515344993274016
360 22925888748079564
361 24426893855968004
362 26024035948649504
363 27723339049775096
364 29531196518630668
365 31454393189029198
366 33500128845762538
367 35676043037975057
368 37990241386823580
369 40451323390965648
370 43068411898387139
371 45851184255657044
372 48809905318091042
373 51955462334754143
374 55299401911377648
375 58853969071321358
376 62632148632825708
377 66647708933679592
378 70915248140807663
379 75450243181566679
380 80269101559768330
381 85389216102425168
382 90829022920897940
383 96608062648063552
384 102747045260207854
385 109267918555151285
386 116193940628468081
387 123549756432867717
388 131361478790740515
389 139656773966832031
390 148464952203825326
391 157817063343799035
392 167745997981434572
393 178286594291785236
394 189475751016754883
395 201352546783450382
396 213958366281776208
397 227337033499209649
398 241534952596176600
399 256601256648720349
400 272587964893856610
401 289550148746135373
402 307546107278083416
403 326637552470151794
404 346889804995891907
405 368372000889330595
406 391157309930671877
407 415323166154653879
408 440951511393911516
409 468129052316003542
410 496947531961873256
411 527504016303320810
412 559901196922420309
413 594247710408921647
414 630658475680276503
415 669255049898433428
416 710166004313024352
417 753527320788462579
418 799482810472883653
419 848184555473513266
420 899793375132387580
421 954479317877778684
422 1012422180409401598
423 1073812055309866109
424 1138849909013070346
425 1207748191367911030
426 1280731478910055446
427 1358037153235448109
428 1439916116804479035
429 1526633547734000082
430 1618469696137843952
431 1715720723771556605
432 1818699589785883224
433 1927736984560531031
434 2043182314708128723
435 2165404741446849612
436 2294794275742104673
437 2431762932685590244
438 2576745948838871570
439 2730203065307406991
440 2892619880649732667
441 3064509276701121488
442 3246412921831714121
443 3438902855084589860
444 3642583156151570491
445 3858091705040198787
446 4086102036889974682
447 4327325296222020601
448 4582512296634860998
449 4852455690726729921
450 5137992256843357348
451 5440005307987934466
452 5759427230156062789
453 6097242156021902227
454 6454488781977964990
455 6832263335126220508
456 7231722699007555824
457 7654087705422553857
458 8100646602012319534
459 8572758703755941496
460 9071858239038583701
461 9599458399353907839
462 10157155604343971383
463 10746633992261922373
464 11369670148732326417
465 12028138084986139191
466 12724014479756172726
467 13459384197233394336
468 14236446096671512369
469 15057519147417724147
470 15925048866514524220
471 16841614094128529210
472 17809934125694021972
473 18832876217674120100
474 19913463487697761058
475 21054883227827621967
476 22260495653787318091
477 23533843110898301530
478 24878659761869498692
479 26298881779403301389
480 27798658071254442700
481 29382361563189839649
482 31054601070236801852
483 32820233784353590931
484 34684378411981402465
485 36652428992580603931
486 38730069434930397742
487 40923288805619918371
488 43238397410163661774
489 45682043704775540028
490 48261232083307285565
491 50983341581360687393
492 53856145546494879123
493 56887832320979844673
494 60087026990867171261
495 63462814252659480978
496 67024762456745505374
497 70782948884195480379
498 74747986321948946263
499 78931050998911819887
500 83343911954427403838
501 87998961908093405880
502 92909249709532641374
503 98088514444178523114
504 103551221281464186051
505 109312599149359313816
506 115388680330167986917
507 121796342070140053068
508 128553350307257270667
509 135678405619188828019
510 143191191506087971170
511 151112425120700383090
512 159463910571742109351
513 168268594924474890522
514 177550627036922624573
515 187335419368211655651
516 197649712911123909545
517 208521645399246690480
518 219980822955735414737
519 232058395349293072289
520 244787135040869088035
521 258201520203347764954
522 272337821915765734480
523 287234195732747489135
524 302930777850421006237
525 319469786089685283575
526 336895625939840665240
527 355255001905542592744
528 374597034423902529889
529 394973382619067288654
530 416438373187130725477
531 439049135705427388552
532 462865744687726598188
533 487951368708606525094
534 514372426949927988311
535 542198753524888446708
536 571503769966893277540
537 602364666274038457752
538 634862590934184726740
539 669082850360038406910
540 705115118200578054678
541 743053655000732210498
542 782997538720839766099
543 825050906634400235206
544 869323209165293609870
545 915929476233931491625
546 964990596727930464673
547 1016633611722762270124
548 1070992022127418460868
549 1128206111441952425591
550 1188423284367179697189
551 1251798422020529213529
552 1318494254569826771638
553 1388681752112694677201
554 1462540534691457716125
555 1540259302352043210738
556 1622036286222415134893
557 1708079721607347045546
558 1798608344168923531974
559 1893851910286435189121
560 1994051742767570915407
561 2099461303110752217762
562 2210346791602836656772
563 2326987776568068336708
564 2449677854175549405102
565 2578725340248264741995
566 2714453995615327181491
567 2857203786589814914589
568 3007331682261018896249
569 3165212490335717991764
570 3331239733378447784941
571 3505826567352097479266
572 3689406744484790079481
573 3882435622547000317834
574 4085391222757439722066
575 4298775338601165689578
576 4523114697989259638830
577 4758962181261854089989
578 5006898097694056756439
579 5267531523245595704764
580 5541501702465488520874
581 5829479517553656954278
582 6132169027766281482970
583 6450309082452378172602
584 6784675011209177360790
585 7136080394756306898034
586 7505378920345135194608
587 7893466325644564664003
588 8301282435279252735929
589 8729813294334616974074
590 9180093403397179308110
591 9653208059852699829246
592 10150295810439563333602
593 10672551020225438330866
594 11221226563473615795256
595 11797636642053865704860
596 12403159737376046528065
597 13039241702033580050876
598 13707398997693976027688
599 14409222086004545537268
600 15146378979661341747439
601 15920618961043994981568
602 16733776476231065204222
603 17587775212492027133735
604 18484632367798167042999
605 19426463121205293507514
606 20415485313445417894438
607 21454024347406428799879
608 22544518318704126186165
609 23689523386928052920944
610 24891719398711786588063
611 26153915774193724331303
612 27479057669052289434527
613 28870232424755964393191
614 30330676320339110330662
615 31863781639517031944717
616 33473104067680609792267
617 35162370433863509110441
618 36935486813564058104282
619 38796547008910495509555
620 40749841423514851518572
621 42799866350027373024180
622 44951333689332217783865
623 47209181121057371124900
624 49578582746080126369674
625 52064960222512234473476
626 54673994417743672887277
627 57411637600004919206255
628 60284126194095153793231
629 63297994126890231797371
630 66460086789533594267351
631 69777575644271744189190
632 73257973505295987692500
633 76909150524112189333473
634 80739350911479260222759
635 84757210429228307766294
636 88971774686923573875511
637 93392518279717321622593
638 98029364805541845031299
639 102892707801304615397739
640 107993432639696045948101
641 113342939429886452584351
642 118953166967498870736921
643 124836617781067142005220
644 131006384324480315431632
645 137476176366907891415661
646 144260349634187471173041
647 151373935757836708636961
648 158832673590551647012918
649 166653041949435662599123
650 174852293851135752310818
651 183448492305665852630156
652 192460547738879729647897
653 201908257116400529038751
654 211812344845269565382497
655 222194505532682630023668
656 233077448684934781423037
657 244484945433085451126013
658 256441877375928932955329
659 268974287634558071237777
660 282109434217230841830741
661 295875845797289627849900
662 310303380011684874701083
663 325423284392062691682199
664 341268260045588076181804
665 357872528207485316262967
666 375271899792934927287930
667 393503848081211457765537
668 412607584671089963920775
669 432624138852267608789516
670 453596440544214985592904
671 475569406960107841121291
672 498590033160727550924780
673 522707486670015073836135
674 547973206331821182840457
675 574441005594801436122249
676 602167180420933075648831
677 631210622021201800309493
678 661632934631262541379878
679 693498558548669613514048
680 726874898663319878836737
681 761832458722326569705993
682 798444981581446373896650
683 836789595705610221893168
684 876946968192941886836659
685 919001464608001549271987
686 963041315922835880482779
687 1009158792876773658810800
688 1057450388079843961753098
689 1108017006198146235625578
690 1160964162574624577640228
691 1216402190653337381170458
692 1274446458591725524610071
693 1335217595461308448982431
694 1398841727455044652648735
695 1465450724536921451159477
696 1535182457988657186745668
697 1608181069327247252112002
698 1684597251088046525116982
699 1764588539988577110591788
700 1848319623010990125566786
701 1935962656963400373589387
702 2027697602104978488554003
703 2123712570443919734573626
704 2224204189344167063240587
705 2329377981103108325724114
706 2439448759191491844113322
707 2554641041875439254016436
708 2675189483971911747294326
709 2801339327520105519412228
710 2933346872185393372810589
711 3071479966246241649484855
712 3216018519051557484903877
713 3367255035872660177445221
714 3525495176114218380228077
715 3691058335888405844393538
716 3864278256000065298304818
717 4045503656434017207390672
718 4235098898482856869815349
719 4433444675700662909728011
720 4640938734919218111440336
721 4857996628614468456857216
722 5085052499966432562718977
723 5322559902011279301921643
724 5570992652344443195215734
725 5830845724893908338641336
726 6102636180347991130827023
727 6386904136887366742467926
728 6684213782941757581237770
729 6995154433762696034491228
730 7320341633680374064305366
731 7660418305989639726146174
732 8016055952493212563269107
733 8387955904813796174952185
734 8776850629676727833088443
735 9183505090455510585630836
736 9608718167370059113196024
737 10053324138825894611027457
738 10518194226488148065142787
739 11004238206790974810066308
740 11512406091697424864481204
741 12043689881640581716757785
742 12599125393700769009527254
743 13179794168199174335296702
744 13786825457022548757293934
745 14421398297129784252837506
746 15084743672836660322379837
747 15778146770622656402530523
748 16502949330361316017437617
749 17260552097035671439651940
750 18052417377170910855542698
751 18880071704389938259894639
752 19745108618682314301314465
753 20649191564165078631435629
754 21594056910314120658612061
755 22581517101848527873436692
756 23613463942667079271535586
757 24691872019456863206642512
758 25818802270828671869611627
759 26996405708073075491525370
760 28226927293885156051828738
761 29512709985665090984762540
762 30856198950276829003846618
763 32259945957427912110130032
764 33726613959131241140437174
765 35258981863013751265242203
766 36859949507559252539242071
767 38532542847702133517084467
768 40279919359537443291904733
769 42105373673269655284404839
770 44012343443899924065065698
771 46004415469537996367068158
772 48085332067633472777036709
773 50258997719839442916798066
774 52529485996663581115605644
775 54901046773514703526505568
776 57378113750231101953818391
777 59965312286667267676329952
778 62667467567433126237414134
779 65489613109410626106015038
780 68436999626232377803681035
781 71515104264481475049149405
782 74729640226977252608048983
783 78086566799133408076360387
784 81592099795030011635632511
785 85252722440513662766846357
786 89075196711348593519349179
787 93066575145169454926097120
788 97234213146752811983593505
789 101585781806911950213719397
790 106129281256148292281462369
791 110873054575044750917334604
792 115825802284282442170104024
793 120996597438083866942908983
794 126394901345854577875795531
795 132030579947792273682567252
796 137913920871279837562472306
797 144055651195957046597805084
798 150466955956498200256017818
799 157159497413288953614810949
800 164145435122419901940493678
801 171437446837675349742219908
802 179048750278519049552316856
803 186993125799442021982860908
804 195284939997467903547269649
805 203939170296085249515277183
806 212971430545422063097267531
807 222397997680071278736098709
808 232235839477646505411890177
809 242502643462869795302269906
810 253216847003798422848107543
811 264397668648659429239113412
812 276065140753711243771355661
813 288240143454563847178291184
814 300944440035496403500880111
815 314200713753485774406478062
816 328032606175936125277814731
817 342464757093449577947570466
818 357522846071437401762049936
819 373233635706910127760234388
820 389625016659441745969897170
821 406726054528046165664248252
822 424567038648573712684514395
823 443179532889198779100175777
824 462596428524668950908023880
825 482851999273187010632337436
826 503981958583144193364039091
827 526023519260380639965453937
828 549015455530263261590503639
829 572998167632605567061759211
830 598013749051356594342999493
831 624106056485019000600105037
832 651320782667969995603554531
833 679705532157213782239316156
834 709309900203643270473650756
835 740185554831591250301750524
836 772386322255362098347758270
837 805968275766512240596789870
838 840989828230948686950496314
839 877511828340396216556882114
840 915597660768505652146451413
841 955313350387792770715508607
842 996727670709772927769957019
843 1039912256717043556000713547
844 1084941722262731418746381759
845 1131893782219615296948981853
846 1180849379568426901472393523
847 1231892817622272968264512305
848 1285111897591882119845330626
849 1340598061704409263208889487
850 1398446542096903800073207940
851 1458756515714212036576188136
852 1521631265450118289876733081
853 1587178347779877745531411657
854 1655509767142040186296925471
855 1726742157337549986270285504
856 1800996970224621171730992072
857 1878400671998767655427881078
858 1959084947358709077139213926
859 2043186911870610825965374124
860 2130849332855348154979532447
861 2222220859136145766352087110
862 2317456259997135683505236666
863 2416716673717032536938280523
864 2520169866056351258270715830
865 2627990499091320417919009668
866 2740360410802984677531795922
867 2857468905845872927008089314
868 2979513057937149424058285102
869 3106698024324292393031755972
870 3239237372807178465195321826
871 3377353421808918611654588172
872 3521277594009017965095876153
873 3671250784072342689112234071
874 3827523741028103955023963176
875 3990357465874534481094062912
876 4160023625007275600485229364
877 4336804980092632553441379814
878 4520995835030937945895980161
879 4712902500680206132447224958
880 4912843778036216924098270398
881 5121151460592051336904912116
882 5338170856628074892506079396
883 5564261332212338820650634729
884 5799796875721513988066292083
885 6045166684723698016000607398
886 6300775776096918541679478507
887 6567045620290804288843723608
888 6844414800673895009073909238
889 7133339698945318551694826853
890 7434295207627271876639089037
891 7747775470693807897394759435
892 8074294653432054641072582478
893 8414387742674080444138793367
894 8768611378581382004713038447
895 9137544719209312054351658498
896 9521790339125904067890458998
897 9921975163408391979437962714
898 10338751438391498237364457292
899 10772797740594171058441591236
900 11224820025306138292877425710
901 11695552716372306322280499820
902 12185759838771927204644182836
903 12696236195650479787746821965
904 13227808591525632999651059514
905 13781337103454374446630852945
906 14357716402016681036205611452
907 14957877124041871504573585486
908 15582787299077314321954997649
909 16233453831675358327906130888
910 16910924041653523662037542232
911 17616287264565026006814865814
912 18350676514701940268447887725
913 19115270213041628502258368494
914 19911293982638810759576574862
915 20740022514060734098162657697
916 21602781503561661747245468746
917 22500949666795248665425298044
918 23435960830969678190281500669
919 24409306108460594276500613130
920 25422536155011281928898612224
921 26477263515768112483758071674
922 27575165062522408414653678785
923 28717984525657482824486566953
924 29907535124432122397934521382
925 31145702299369098739168967606
926 32434446550659886277540961164
927 33775806386644526450537851858
928 35171901386579007115155689754
929 36624935382061516543167897985
930 38137199761654009051382392091
931 39711076903406580191335162334
932 41349043740169747859294885924
933 43053675462763771002257231334
934 44827649366265193612467022466
935 46673748844868781921083107090
936 48594867540988542474236519031
937 50594013654474476064611330203
938 52674314418042786110320120386
939 54839020745246333636065130242
940 57091512057549898232108352285
941 59435301297321185540505229388
942 61874040133804237989970575473
943 64411524369406884098316221102
944 67051699553908863414188013277
945 69798666814482225072242610052
946 72656688909711320170817668722
947 75630196516106137672677107491
948 78723794755920716748088997613
949 81942269975417861959551138514
950 85290596783063285048751339561
951 88773945357486567210860284775
952 92397689035413921570731069725
953 96167412190158620115677750423
954 100088918411650128170336600391
955 104168238999392460731881567427
956 108411641780167090307547910359
957 112825640262735910638892134386
958 117417003142256405330077255871
959 122192764167594319747509347434
960 127160232385209961774015944261
961 132327002773802817782022224290
962 137700967284426704561890555351
963 143290326301334265049159185592
964 149103600539376565733032466298
965 155149643394370972091337271858
966 161437653763459750238905822281
967 167977189353113101916632775143
968 174778180493085050773484536143
969 181850944475308925694498207441
970 189206200437422680381130923059
971 196855084811343147617845556952
972 204809167358064189655134136842
973 213080467810636810579938873614
974 221681473148101375859547462881
975 230625155523983417517463326621
976 239924990873836924496691409915
977 249594978227222851761352240341
978 259649659750447769325564422975
979 270104141547358488085458195794
980 280974115246495198057536094980
981 292275880403948564863916892876
982 304026367752347527452701485120
983 316243163327524712343938245889
984 328944533505567730623104593168
985 342149450984167705856046389950
986 355877621743423634494514979413
987 370149513022553227536501982089
988 384986382350300308155594113661
989 400410307668216344126514498663
990 416444218587432014789417209758
991 433111928821024632139401802464
992 450438169835631657401918090470
993 468448625767560350167492344870
994 487169969650301833503341808560
995 506629901002075526086465247226
996 526857184823810242653552077170
997 547881692059812373515850791625
998 569734441575282881376077082222
999 592447643706824590544454313275
1000 616054745444133057672570053521