0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 55
12 75
13 98
14 130
15 168
16 219
17 279
18 359
19 453
20 575
21 720
22 904
23 1122
24 1397
25 1722
26 2125
27 2603
28 3190
29 3883
30 4729
31 5725
32 6930
33 8349
34 10053
35 12053
36 14444
37 17243
38 20569
39 24457
40 29055
41 34414
42 40728
43 48070
44 56683
45 66682
46 78366
47 91897
48 107663
49 125880
50 147036
51 171436
52 199690
53 232207
54 269765
55 312904
56 362600
57 419581
58 485065
59 560005
60 645946
61 744120
62 856460
63 984583
64 1130897
65 1297484
66 1487371
67 1703219
68 1948805
69 2227548
70 2544141
71 2902929
72 3309779
73 3770182
74 4291420
75 4880457
76 5546310
77 6297738
78 7145940
79 8101885
80 9179422
81 10392301
82 11757602
83 13292473
84 15018010
85 16955521
86 19130966
87 21570830
88 24306999
89 27372247
90 30805754
91 34647966
92 38946892
93 43752426
94 49123275
95 55120789
96 61816755
97 69286426
98 77617375
99 86901837
100 97246465
101 108764006
102 121584276
103 135844826
104 151703353
105 169327495
106 188908516
107 210650280
108 234784600
109 261558940
110 291253763
111 324169145
112 360643928
113 401041300
114 445770263
115 495269696
116 550032533
117 610588529
118 677530980
119 751498283
120 833203868
121 923415935
122 1022991166
123 1132852960
124 1254028737
125 1387626817
126 1534878186
127 1697111367
128 1875799381
129 2072532981
130 2289072742
131 2527320900
132 2789379694
133 3077521060
134 3394252226
135 3742283870
136 4124602960
137 4544439720
138 5005349260
139 5511176580
140 6066148363
141 6674836800
142 7342261790
143 8073854206
144 8875570490
145 9753854631
146 10715767071
147 11768946585
148 12921754058
149 14183235168
150 15563281839
151 17072595170
152 18722867196
153 20526745760
154 22498037718
155 24651677328
156 27003954650
157 29572487198
158 32376477302
159 35436689592
160 38775739352
161 42418078184
162 46390318648
163 50721228593
164 55442097315
165 60586742388
166 66191920783
167 72297352004
168 78946181496
169 86185021637
170 94064475073
171 102639199354
172 111968495710
173 122116403183
174 133152363220
175 145151346948
176 158194606409
177 172369843603
178 187772057210
179 204503762488
180 222675948230
181 242408354170
182 263830553899
183 287082302887
184 312314760930
185 339690924716
186 369387010915
187 401592984999
188 436514127633
189 474371679225
190 515404610645
191 559870404790
192 608047061840
193 660234037064
194 716754513540
195 777956525607
196 844215530704
197 915935750560
198 993553085790
199 1077536705735
200 1168392353578
201 1266664228455
202 1372938728840
203 1487846675346
204 1612067555120
205 1746332133717
206 1891427269915
207 2048198981691
208 2217557902525
209 2400482873590
210 2598027132457
211 2811322506075
212 3041586432486
213 3290126850683
214 3558350160727
215 3847766918034
216 4160000862935
217 4496795532475
218 4860024505534
219 5251699073920
220 5673979858311
221 6129185697314
222 6619806823693
223 7148515141560
224 7718179174140
225 8331875937220
226 8992907886200
227 9704816619514
228 10471402098074
229 11296738431643
230 12185195676464
231 13141458009100
232 14170548434425
233 15277849688906
234 16469132252545
235 17750578355762
236 19128813736064
237 20610935191905
238 22204546567069
239 23917790350235
240 25759388453026
241 27738678403820
242 29865659554269
243 32151034511138
244 34606261469985
245 37243601608855
246 40076178361576
247 43118031573800
248 46384184627229
249 49890706288280
250 53654786691371
251 57694807926880
252 62030430046755
253 66682671552807
254 71674006730280
255 77028457377236
256 82771702914139
257 88931184861422
258 95536231387612
259 102618176211634
260 110210499454879
261 118348962892279
262 127071769182461
263 136419715630590
264 146436374165765
265 157168266025356
266 168665065138230
267 180979796483622
268 194169065840393
269 208293284912518
270 223416930813621
271 239608801408942
272 256942308313508
273 275495766375552
274 295352724400680
275 316602293183749
276 339339518736691
277 363665753787932
278 389689078870570
279 417524722868285
280 447295537939150
281 479132475366640
282 513175121078230
283 549572233791545
284 588482348700535
285 630074385821243
286 674528330297216
287 722035919806872
288 772801411024720
289 827042355987582
290 884990465391354
291 946892485082431
292 1013011168109121
293 1083626263846766
294 1159035612225910
295 1239556259461608
296 1325525689478310
297 1417303081970300
298 1515270697787106
299 1619835296929958
300 1731429696739796
301 1850514369486080
302 1977579194429422
303 2113145257091782
304 2257766818705442
305 2412033341870528
306 2576571703775581
307 2752048475819050
308 2939172410087423
309 3138697003877495
310 3351423292323404
311 3578202732396234
312 3819940338535209
313 4077597924700446
314 4352197624166701
315 4644825532844421
316 4956635659127220
317 5288854016740380
318 5642783055998225
319 6019806259995600
320 6421393114584590
321 6849104268114479
322 7304597103998379
323 7789631531184493
324 8306076230700391
325 8855915151730363
326 9441254511744680
327 10064330081848567
328 10727515029169338
329 11433328084763540
330 12184442327263338
331 12983694337250330
332 13834094032478595
333 14738834924691083
334 15701305129232200
335 16725098853523645
336 17814028718039540
337 18972138620280070
338 20203717519631346
339 21513313837214880
340 22905750874327969
341 24386142926719976
342 25959912525692640
343 27632808465436080
344 29410925077178467
345 31300722390836539
346 33309047676153690
347 35443157984810661
348 37710744218971322
349 40119956327504213
350 42679430191503488
351 45398315779160360
352 48286307170035277
353 51353674007128707
354 54611295017793882
355 58070693139147208
356 61744072933286394
357 65644359804268381
358 69785241749256198
359 74181213131669068
360 78847621259034390
361 83800715228162972
362 89057697874652540
363 94636780263189614
364 100557239613503307
365 106839480071994428
366 113505097285722081
367 120576946161282075
368 128079212832023850
369 136037490187813900
370 144478858062008667
371 153431967401420686
372 162927129590133962
373 172996410223633640
374 183673728586396225
375 194994962099452176
376 206998057078952383
377 219723145042535883
378 233212665998662299
379 247511497925371688
380 262667093975321558
381 278729626582952119
382 295752140119381741
383 313790711241018400
384 332904618694095150
385 353156521691104639
386 374612648747346975
387 397342996063848838
388 421421537479806466
389 446926445052606598
390 473940322433434072
391 502550450068900008
392 532849044553292171
393 564933531135432840
394 598906831872670347
395 634877668412163404
396 672960882072449595
397 713277770183329980
398 755956441552242947
399 801132189995489582
400 848947889012067717
401 899554406523018115
402 953111042979544750
403 1009785991750667197
404 1069756825337678200
405 1133211006318346917
406 1200346426830505990
407 1271371975496588120
408 1346508135881359998
409 1425987615388681197
410 1510056008995514936
411 1598972496740239180
412 1693010579692898883
413 1792458853345224881
414 1897621823503295148
415 2008820763650340750
416 2126394619247387740
417 2250700957979572680
418 2382116971830632579
419 2521040530047576640
420 2667891289325844293
421 2823111860344570914
422 2987169037467648969
423 3160555090823574308
424 3343789128103591655
425 3537418525394202012
426 3742020434949626260
427 3958203369343054913
428 4186608870516205150
429 4427913263311535377
430 4682829502669943809
431 4952109114251475314
432 5236544238379369688
433 5536969777266387925
434 5854265656202343678
435 6189359198895449429
436 6543227628488486095
437 6916900694714494600
438 7311463439624731491
439 7728059102665481550
440 8167892178526347779
441 8632231628893624776
442 9122414262603020446
443 9639848285735198142
444 10186017037309657205
445 10762482912585708977
446 11370891490887487234
447 12012975870489428201
448 12690561228845970026
449 13405569611301772560
450 14160024968048466718
451 14956058443140422490
452 15795913936946398757
453 16681953946611269695
454 17616665707651532510
455 18602667642118432552
456 19642716138348097270
457 20739712668696414825
458 21896711272339070272
459 23116926410614676995
460 24403741224228011496
461 25760716201003625840
462 27191598285935534901
463 28700330443576958281
464 30291061707157288195
465 31968157725981162104
466 33736211848365108469
467 35600056753354930540
468 37564776671595609622
469 39635720210475737775
470 41818513827308716980
471 44119075967762827753
472 46543631916985986630
473 49098729382964513497
474 51791254863565698763
475 54628450819386208143
476 57617933708213476448
477 60767712906087427483
478 64086210575505958810
479 67582282508942548830
480 71265240013369673079
481 75144872867478434290
482 79231473422894173745
483 83535861884976882740
484 88069412850602112835
485 92844083142828566784
486 97872441026478949916
487 103167696849310962480
488 108743735200024008157
489 114615148633048639702
490 120797273059216589549
491 127306224858082664965
492 134158939819539900089
493 141373213976924002436
494 148967746448550988315
495 156962184356969311936
496 165377169952991404981
497 174234390021602048514
498 183556627707822709818
499 193367816848238217766
500 203693098958258546543
501 214558882970301928240
502 225992907886023459555
503 238024308448216613172
504 250683684009716995500
505 264003170716420729548
506 278016517197215809190
507 292759163890568870453
508 308268326217401127138
509 324583081743887473935
510 341744461562137874300
511 359795546047657016610
512 378781565241497168501
513 398750004032764053100
514 419750712411110897467
515 441836020983295872152
516 465060862047081540350
517 489482896436761898459
518 515162646459341880812
519 542163635157830392782
520 570552532248695188363
521 600399306994273824395
522 631777388387693852911
523 664763832937775302172
524 699439500464684271688
525 735889238223055279319
526 774202073799504256814
527 814471417133307713631
528 856795272146522737021
529 901276458367440132138
530 948022843076491211193
531 997147584396960465520
532 1048769385906257159930
533 1103012763232219308255
534 1160008323260959094770
535 1219893056466825579008
536 1282810643046248269978
537 1348911773416487668514
538 1418354483821189246670
539 1491304507658973636952
540 1567935643342402842782
541 1648430139363933864481
542 1732979097447432817580
543 1821782894527883939926
544 1915051624515380110789
545 2013005560658221082105
546 2115875639545553965410
547 2223903967643281162800
548 2337344351495465325291
549 2456462852571170680680
550 2581538367988844578998
551 2712863238192380441680
552 2850743882919629318607
553 2995501466640386941765
554 3147472594922858892702
555 3307010043017981694819
556 3474483518249223242155
557 3650280457619918491360
558 3834806862365678933346
559 4028488170997835253415
560 4231770172717661029228
561 4445119962893468864729
562 4669026942645875510728
563 4904003864392791604708
564 5150587925579483326441
565 5409341912619214923560
566 5680855397465648715145
567 5965745989032240159633
568 6264660642092753424327
569 6578277026085051265373
570 6907304956683839303679
571 7252487892790109508640
572 7614604502054752000195
573 7994470297829993296176
574 8392939350939871883426
575 8810906079431450229128
576 9249307119995566801139
577 9709123284510904872594
578 10191381605723701947890
579 10697157475835098661374
580 11227576882360097850926
581 11783818745376805140190
582 12367117360912117604395
583 12978764954960101241089
584 13620114353294614754347
585 14292581771983580514257
586 14997649734217857077351
587 15736870118809807628677
588 16511867346465010108560
589 17324341709669561269180
590 18176072852829375860722
591 19068923409034394417746
592 20004842800663108883201
593 20985871210777635947860
594 22014143733153742708695
595 23091894708524227533539
596 24221462255563330929196
597 25405293004873994725908
598 26645947045247765843250
599 27946103091202599767708
600 29308563881874340911967
601 30736261821075700537780
602 32232264869473801520071
603 33799782699579392252563
604 35442173125449231857365
605 37162948818750828777212
606 38965784324122977736030
607 40854523386520665644977
608 42833186604598170811120
609 44905979423948734254377
610 47077300485470861705940
611 49351750343907596193791
612 51734140573149001536975
613 54229503274678600337338
614 56843101007186929933518
615 59580437155182847064420
616 62447266756180839050895
617 65449607805870166661219
618 68593753062531636047325
619 71886282371818869136982
620 75334075535001010046026
621 78944325743642114393679
622 82724553605800874867944
623 86682621788744108700310
624 90826750305412983402207
625 95165532471826779592736
626 99707951565001237506815
627 104463398210945425088072
628 109441688534850183507989
629 114653083105614802967320
630 120108306709575448387885
631 125818568988385274392760
632 131795585978892575834742
633 138051602593009244082455
634 144599416078650319216590
635 151452400503038312883798
636 158624532302960065342226
637 166130416946851834964720
638 173985316757102549656648
639 182205179941336956749983
640 190806670885190339110416
641 199807201759551939907920
642 209224965499256531690849
643 219078970210773330185501
644 229389075070714142228387
645 240176027777668262295128
646 251461503624433987955736
647 263268146258530901087860
648 275619610203749736844521
649 288540605216453456582667
650 302056942555548474500251
651 316195583246159385353821
652 330984688422602425953906
653 346453671837541523032660
654 362633254630154837657860
655 379555522447620566367155
656 397253985020584686498719
657 415763638294965985388315
658 435121029229247158420950
659 455364323368326711299920
660 476533375312271172268579
661 498669802200489651764615
662 521817060339623250860410
663 546020525105906215006640
664 571327574261068701633430
665 597787674823624985722675
666 625452473646285919602452
667 654375891853347965699788
668 684614223301430807684477
669 716226237230421129114910
670 749273285281670269545847
671 783819413064386696161289
672 819931476462073892579045
673 857679262875203626406639
674 897135617607996780631340
675 938376575612011150870246
676 981481498811747248550014
677 1026533219242843748110969
678 1073618188246836329914662
679 1122826631972396895672427
680 1174252713447328618235197
681 1227994701492171491924080
682 1284155146761658602884106
683 1342841065207536635439019
684 1404164129272752698436740
685 1468240867135039783303205
686 1535192870335606679328981
687 1605147010137493364554880
688 1678235662977099283277539
689 1754596945382146077436608
690 1834374958749650092657110
691 1917720044388213082656080
692 2004789049250722544036390
693 2095745602795351707209827
694 2190760405436110864373368
695 2290011529057159810517825
696 2393684730090149033553961
697 2501973775668076460900226
698 2615080783396027376375269
699 2733216575294755212972022
700 2856601046501900782419968
701 2985463549332727701102914
702 3120043293333196956269240
703 3260589761976902588234770
704 3407363146690598639297636
705 3560634798913504518674809
706 3720687700931216438643685
707 3887816956247418356068467
708 4062330300294840709394000
709 4244548632311352624856000
710 4434806569248138599155219
711 4633453022603595554828680
712 4840851799120672663700464
713 5057382226314499222923647
714 5283439803844480007881385
715 5519436881776804005145928
716 5765803366834138174053860
717 6022987457763909951881460
718 6291456411011161675281168
719 6571697337919697963065280
720 6864218034743862028929790
721 7169547846794379732895392
722 7488238568104664005750468
723 7820865378048719809349160
724 8168027816409408548192807
725 8530350798444525519935700
726 8908485671570778134619956
727 9303111315338720640396828
728 9714935286449727966124433
729 10144695010623684556096715
730 10593159023209889124675605
731 11061128260496275045290475
732 11549437403762105150249195
733 12058956278187313996875058
734 12590591308828432870996460
735 13145287035944904699932656
736 13724027692063565514461405
737 14327838843249276065551686
738 14957789097161405766674064
739 15614991880562927733149560
740 16300607289068934482558983
741 17015844012015844816992686
742 17761961335461581997788390
743 18540271226429467320564152
744 19352140501647215030734867
745 20198993084143526589249396
746 21082312351213780965549580
747 22003643577386772885310770
748 22964596476184585006556690
749 23966847844598228230257770
750 25012144314373790498647412
751 26102305214345283241908076
752 27239225548235352952873640
753 28424879092498244736466750
754 29661321618978222206789363
755 30950694247322576005308656
756 32295226932302049147958029
757 33697242091371153805004339
758 35159158378030546095594290
759 36683494606748077988495960
760 38272873835442034122446079
761 39930027611740492060412041
762 41657800389496120122881470
763 43459154122263397492823608
764 45337173040730491067236770
765 47295068621344292146136072
766 49336184753673730197377240
767 51464003114322810683872275
768 53682148755534403513590645
769 55994395916913773976048522
770 58404674069055114194774928
771 60917074198165628375515589
772 63535855341162526622885814
773 66265451381054731740530974
774 69110478112830426245541130
775 72075740590435133612331418
776 75166240765865006425946955
777 78387185431792789716684700
778 81743994479616854734644208
779 85242309485247995696587742
780 88888002635457019687896088
781 92687186008064403352091454
782 96646221219799684259835931
783 100771729456153073654114480
784 105070601898129069518510688
785 109550010561346071946559749
786 114217419563557244513831534
787 119080596837244534254518412
788 124147626304616232377213033
789 129426920532960843127865823
790 134927233889039245562992593
791 140657676211868752331665830
792 146627727024036414465073745
793 152847250302403555833149820
794 159326509829905853251936720
795 166076185150934992848053024
796 173107388153693211589176210
797 180431680303755197877291548
798 188061090554044728781849292
799 196008133957342733483333306
800 204285831008489026767722521
801 212907727744420462651699029
802 221887916631311857183355275
803 231241058269143155158206920
804 240982403945223749393646152
805 251127819069344435050250666
806 261693807524524967213509596
807 272697536968553474080771552
808 284156865122908187872456613
809 296090367086975679050045437
810 308517363716977874288698362
811 321457951110446529130198054
812 334933031238693493328974540
813 348964343771261927541494840
814 363574499138073118164274880
815 378787012876639127459901932
816 394626341313569676998879496
817 411117918631384977783465329
818 428288195373642554086420872
819 446164678443306764701215747
820 464775972651434424312202776
821 484151823875318253081562826
822 504323163887533882453215299
823 525322156919563226548361905
824 547182248026142063541331075
825 569938213318877411454304365
826 593626212140338940433769690
827 618283841252409841645900255
828 643950191115538355855903458
829 670665904338309497212299796
830 698473236379823901960775299
831 727416118590360940214126564
832 757540223679097771090626530
833 788893033700873907551147000
834 821523910657529210809929410
835 855484169812805754139112142
836 890827155823604034068387005
837 927608321794109355480369075
838 965885311363385106315543040
839 1005718043941037339189492798
840 1047168803209937370076703903
841 1090302329019300105284124640
842 1135185912796121544982135848
843 1181889496607615682953156888
844 1230485776012343834490927402
845 1281050306842716073401226699
846 1333661616066969682147028865
847 1388401316884091902854290032
848 1445354228210979075293906925
849 1504608498726890098792558985
850 1566255735646505648306931781
851 1630391138399103637807050959
852 1697113637398074826659124449
853 1766526038091666636392047329
854 1838735170493050018162425250
855 1913852044394967694247401480
856 1991992010481958103220583159
857 2073274927560848848528318600
858 2157825336138517125843338913
859 2245772638584189381948080055
860 2337251286122464997377806898
861 2432400972912141023137103040
862 2531366837475480548679136366
863 2634299671752122168141056827
864 2741356138062093868066532893
865 2852698994272660640434763393
866 2968497327474751977463500255
867 3088926796485744393907610950
868 3214169883507196277585790775
869 3344416155277980013278941320
870 3479862534075941963333169514
871 3620713578933946821142451041
872 3767181777449774307528847428
873 3919487848583004303611354645
874 4077861056846630554044554448
875 4242539538315821865153074808
876 4413770638891917871219798050
877 4591811265275509266761019043
878 4776928249119261270844220300
879 4969398724848064550389241710
880 5169510521652129468357000806
881 5377562570176811830153561068
882 5593865324452300585005748354
883 5818741199625807298709894553
884 6052525026079644250479956749
885 6295564520539521041140932562
886 6548220774799642162073922779
887 6810868762713668177641575193
888 7083897866124469166082965318
889 7367712420429727275551448325
890 7662732280506040212723463486
891 7969393407740072401348749480
892 8288148478942748175555758749
893 8619467517950270115293685907
894 8963838550745178353190654128
895 9321768284960485356194601966
896 9693782814661480272093511998
897 10080428351331791268229166141
898 10482271982024132496724573665
899 10899902455670488350821080120
900 11333930998582766939793527723
901 11784992160211779470298591240
902 12253744690271296403631830366
903 12740872448373433559318345057
904 13247085347363316510634468760
905 13773120331583342866385132361
906 14319742391342057336232967052
907 14887745614908099542862135040
908 15477954279397593078929317458
909 16091223981972082455995152812
910 16728442812815474390170246407
911 17390532571410705767201884041
912 18078450027691895681457302220
913 18793188229703783711142921777
914 19535777859459237957874316675
915 20307288638745708731693975223
916 21108830786694710738833760915
917 21941556530992844098164103299
918 22806661674680595889919333254
919 23705387220554234158406499040
920 24639021055258681704318149211
921 25608899695233299093448488720
922 26616410096750267661050741822
923 27662991532364629355092400290
924 28750137536178353254054555670
925 29879397920405865277260600275
926 31052380865817733380134431425
927 32270755088730370706448662647
928 33536252087305236042982757765
929 34850668470018715519809548295
930 36215868369266294827392217819
931 37633785943169331111737553115
932 39106427968762445882085288120
933 40635876529851748328932916349
934 42224291802951609005585562295
935 43873914944827907149699073306
936 45587071085301530808901969915
937 47366172429094691136844415824
938 49213721470637398235767120324
939 51132314325889409651513954880
940 53124644185377303957191400601
941 55193504892794121469773782814
942 57341794653663579157511252405
943 59572519878729171165334575926
944 61888799166893969557836186283
945 64293867432706495460522760072
946 66791080183565235823068597150
947 69383917951995975086064832376
948 72075990888545834242991868825
949 74871043521032383843514317638
950 77772959686089311323781379114
951 80785767639158376562799047063
952 83913645349294826456568289029
953 87160925985376433621504230123
954 90532103600539080736073705200
955 94031839021900574568954050801
956 97664965952883514470972312385
957 101436497295703668823119746140
958 105351631701856975805789231307
959 109415760358711953029449984880
960 113634474020599701317852343088
961 118013570293086649259447409101
962 122559061179420622701954289998
963 127277180898454417367575599065
964 132174393983677914857675899295
965 137257403673325440168982929207
966 142533160601874827972619180995
967 148008871803613915590015468480
968 153692010039324440451905568740
969 159590323457517796715219382917
970 165711845602057547942893718708
971 172064905778415040659544257460
972 178658139791232895092002148755
973 185500501066311432056183142199
974 192601272170591445588842986450
975 199970076744177838948525327688
976 207616891858938972486048592819
977 215552060818720631348353914520
978 223786306416738033217948331145
979 232330744666248577754027643545
980 241196899021169083547428123016
981 250396715103878186611454233840
982 259942575958044660433196953241
983 269847317844939581831103467202
984 280124246602332074740599053503
985 290787154585728529048623984895
986 301850338212401582812889924790
987 313328616129361273977663105070
988 325237348027154797257758671696
989 337592454122136524163404604280
990 350410435330634873504098063450
991 363708394159250311333587219451
992 377504056336358070161309876411
993 391815793210752930253264966397
994 406662644944270814771290852520
995 422064344526145599323706623472
996 438041342637819010557610655730
997 454614833397909126030039541105
998 471806781018068761026348368490
999 489639947401521023031121771448
1000 508137920717155906497660941884