1 1
2 2
3 3
4 4
5 7
6 8
7 15
8 18
9 28
10 35
11 56
12 64
13 101
14 120
15 168
16 210
17 297
18 348
19 490
20 583
21 776
22 946
23 1255
24 1482
25 1952
26 2335
27 2981
28 3581
29 4565
30 5387
31 6842
32 8119
33 10086
34 12013
35 14863
36 17527
37 21637
38 25525
39 31083
40 36695
41 44583
42 52256
43 63261
44 74171
45 88932
46 104303
47 124754
48 145490
49 173511
50 202234
51 239645
52 279151
53 329931
54 382791
55 451215
56 523089
57 613663
58 710655
59 831820
60 960216
61 1121505
62 1293314
63 1504681
64 1733282
65 2012452
66 2312425
67 2679689
68 3075423
69 3553089
70 4072932
71 4697205
72 5373309
73 6185689
74 7067863
75 8116138
76 9263074
77 10619794
78 12098638
79 13848650
80 15758930
81 18001318
82 20461672
83 23338469
84 26486841
85 30167055
86 34199701
87 38883107
88 44032918
89 49995925
90 56539265
91 64112245
92 72428247
93 82003334
94 92544966
95 104650924
96 117958914
97 133230930
98 150024492
99 169219706
100 190364482
101 214481126
102 241013417
103 271248950
104 304519760
105 342309883
106 383946405
107 431149389
108 483099098
109 541946240
110 606711491
111 679881565
112 760475125
113 851376628
114 951410980
115 1064143191
116 1188193026
117 1327678865
118 1481242323
119 1653668355
120 1843344902
121 2056147996
122 2290199407
123 2552293657
124 2840640342
125 3163125395
126 3517664465
127 3913864295
128 4349336971
129 4835208608
130 5369300474
131 5964539504
132 6618433134
133 7346629009
134 8146361006
135 9035743963
136 10012493929
137 11097645016
138 12288683177
139 13610949895
140 15061786003
141 16670564453
142 18435596115
143 20390982602
144 22535115965
145 24908853439
146 27510866910
147 30388497677
148 33542329995
149 37027355200
150 40844909389
151 45060624582
152 49676999314
153 54770096355
154 60346052353
155 66493175250
156 73219832380
157 80630964769
158 88737930152
159 97662398623
160 107422354873
161 118159067159
162 129895517166
163 142798995930
164 156898969038
165 172389338726
166 189311484110
167 207890420102
168 228177664506
169 250438925015
170 274738437727
171 301384187868
172 330461236649
173 362326859895
174 397085476416
175 435157680997
176 476671748973
177 522114999374
178 571651609730
179 625846753120
180 684899778375
181 749474411781
182 819812793511
183 896683696021
184 980390346607
185 1071823752695
186 1171349388876
187 1280011041917
188 1398249075849
189 1527272091147
190 1667622727116
191 1820701100652
192 1987157008779
193 2168627105469
194 2365889510915
195 2580838169165
196 2814420785873
197 3068829878530
198 3345194440100
199 3646072432125
200 3972808423386
201 4328360978957
202 4714352404957
203 5134205283395
204 5589843976629
205 6085253814672
206 6622716459090
207 7206838152119
208 7840351424564
209 8528581301831
210 9274756118914
211 10085065885767
212 10963322928921
213 11916676539072
214 12949664776506
215 14070545636021
216 15284662370832
217 16601598101059
218 18027640570431
219 19573849975455
220 21247671770867
221 23061871173453
222 25025186789039
223 27152408925615
224 29453788931477
225 31946382488936
226 34642274945891
227 37561133582570
228 40717102313559
229 44132934884255
230 47825175497133
231 51820041207988
232 56136959762683
233 60806135438329
234 65850246158874
235 71304185390160
236 77194410589367
237 83561090077220
238 90435185988021
239 97862933703585
240 105880386468547
241 114540884553038
242 123886386928263
243 133978241340562
244 144865401175531
245 156618412339554
246 169294149591635
247 182973889853437
248 197723674741156
249 213636896482155
250 230790391035062
251 249291451168559
252 269229155521876
253 290726957914803
254 313888077442370
255 338854233841511
256 365745215792183
257 394723676655357
258 425928214937779
259 459545750427025
260 495736563165712
261 534715024020910
262 576666710407664
263 621837416509615
264 670441458194867
265 722760953360436
266 779043282907012
267 839611680370888
268 904751959275663
269 974834369944625
270 1050188397167213
271 1131238503938606
272 1218364334262445
273 1312051736671998
274 1412738467528434
275 1520980492397949
276 1637281604567029
277 1762278433057269
278 1896550492641689
279 2040825770564872
280 2195771245244583
281 2362219145337711
282 2540935826811518
283 2732873183547535
284 2938911353636233
285 3160137761883748
286 3397563621000737
287 3652430836026457
288 3925899502867947
289 4219388528586799
290 4534228217332189
291 4872037923241153
292 5234343552701071
293 5622992691950605
294 6039733343346665
295 6486674126247263
296 6965816594776318
297 7479564909277730
298 8030211357587840
299 8620496275463671
300 9253041892162946
301 9930972392340227
302 10657286171924257
303 11435541863340977
304 12269168332940836
305 13162217893936194
306 14118607653917899
307 15142952738857194
308 16239726179078631
309 17414179861898344
310 18671421805124920
311 20017426762576945
312 21458022500587876
313 23000006655487337
314 24650025519865721
315 26415807289646980
316 28304931589217199
317 30326181989842964
318 32488195304791688
319 34800954869436211
320 37274298336855331
321 39919565095850601
322 42747959876781848
323 45772358543577243
324 49005513238216550
325 52462044226814133
326 56156459313878359
327 60105349297720303
328 64325217689639239
329 68834885945949083
330 73653114863019798
331 78801255302666615
332 84300626301402538
333 90175434300646394
334 96449902301782658
335 103151466319055631
336 110307631459939200
337 117949491546113972
338 126108267394868906
339 134819179771924891
340 144117661756180696
341 154043597379569134
342 164637176829522139
343 175943559810249229
344 188008316556793351
345 200882555219985452
346 214617937416426404
347 229272286871217150
348 244904139142114566
349 261578907351144125
350 279362893321729005
351 298330061735045021
352 318555497072463677
353 340122810048577428
354 363116988451036481
355 387632532914332013
356 413765609231736705
357 441622980275449352
358 471313438421645660
359 502957566506000020
360 536678383504543785
361 572612058898037070
362 610897654277472320
363 651688877941048822
364 695142893581754985
365 741433159877895990
366 790737220674394379
367 843250788562528427
368 899174367933207711
369 958728695359999778
370 1022140156536503129
371 1089657644424069838
372 1161536660576630071
373 1238057794119125085
374 1319509319716418275
375 1406207443390240397
376 1498477345248835494
377 1596675274490752127
378 1701167897184113918
379 1812356499739472950
380 1930654404613798062
381 2056513471422769509
382 2190399511722664479
383 2332821198543892336
384 2484303302639224848
385 2645418340677677757
386 2816757334590837323
387 2998964442901180298
388 3192705152410790979
389 3398704041358160275
390 3617710177645984579
391 3850538434667427636
392 4098031721055084096
393 4361106164797744609
394 4640710055869744985
395 4937873096774343000
396 5253661772432466571
397 5589233202595404488
398 5945786468635442472
399 6324621475157050375
400 6727086078726253401
401 7154640222653942321
402 7608798506829859610
403 8091200276484458640
404 8603547044781768975
405 9147679059805280210
406 9725507379536022983
407 10339097267123925550
408 10990594463675114074
409 11682316277192317780
410 12416671317876869417
411 13196258955827790685
412 14023782260531139302
413 14902156290309117135
414 15834413665357693448
415 16823822787115897070
416 17873785129033641750
417 18987964253720714661
418 20170174490224604815
419 21424521360255636320
420 22755280926388212620
421 24167053021441363961
422 25664630128771829079
423 27253164529559732505
424 28938026293377592875
425 30724985147064881792
426 32620056682293399790
427 34629700713902454416
428 36760654291735601412
429 39020147979846235740
430 41415725136522459357
431 43955477170518116534
432 46647847976542757849
433 49501890409405150715
434 52527054127508839259
435 55733465119688545373
436 59131696280987101972
437 62733071376043077472
438 66549416965599269306
439 70593393646562135510
440 74878227171147807239
441 79418069316053225556
442 84227707345858311586
443 89322956321353645667
444 94720345198477381650
445 100437544171702851674
446 106493024752830192966
447 112906525162168748153
448 119698683328168530924
449 126891542690981418000
450 134508156014280571024
451 142573136155347359592
452 151112227428790991157
453 160152905199493091002
454 169723913485324458395
455 179855916453892127921
456 190580999674911302862
457 201933379285114688629
458 213948862899798184877
459 226665621381061006262
460 240123607787613017331
461 254365395758574199975
462 269435553332554737657
463 285381555241961986287
464 302253106734427965450
465 320103136086418104946
466 338987066443389994220
467 358963893768162876613
468 380095402838314499082
469 402447339861708795458
470 426088566711374353499
471 451092336274465135094
472 477535382512271452065
473 505499305314204566243
474 535069591701765406096
475 566337121865700946306
476 599397114345459105105
477 634350763556124300002
478 671304106033798103647
479 710369798236628238005
480 751665898205206080956
481 795317798414758210444
482 841456914201939096417
483 890222784833765466003
484 941761665226554546624
485 996228806608440180077
486 1053786944754300101316
487 1114608778936426484248
488 1178875346288043306185
489 1246778715858473923734
490 1318520244993703607702
491 1394313503224447816939
492 1474382402586742592476
493 1558964374994977801313
494 1648308364092282556876
495 1742678277575201872270
496 1842350835776643209586
497 1947619317987653366789
498 2058791258216653596822
499 2176192515439287461625
500 2300164801780579265281
501 2431070104101396907773
502 2569288039085647120722
503 2715220650772245313220
504 2869289581341515847068
505 3031941282464198651611
506 3203643984369244048653
507 3384893355993910888143
508 3576209266106163347004
509 3778141924035171537110
510 3991268419828920401039
511 4216199393504633912780
512 4453575333821374076597
513 4704073820700791037035
514 4968405575764449664418
515 5247322318923607545021
516 5541612555749568290064
517 5852110108921301536232
518 6179689618692327291344
519 6525275806187325928219
520 6889838679667303068333
521 7274403582551733377346
522 7680046088603945236521
523 8107902911527474124146
524 8559166461765041788980
525 9035096690393497790409
526 9537015300152823511923
527 10066318591787500099449
528 10624471310587280065892
529 11213020592521695110326
530 11833589415244962779600
531 12487891736845405972431
532 13177725544423885783486
533 13904989273245567290330
534 14671674432657401255925
535 15479883428970329919565
536 16331821733969593177427
537 17229817229991363967478
538 18176311915556491490409
539 19173882885687443690738
540 20225233553526277479245
541 21333216422211708570598
542 22500823784338852226887
543 23731212436596895726573
544 25027693854446929293970
545 26393760995004841021909
546 27833077926008223622610
547 29349508915133986374841
548 30947107472467909928424
549 32630147919266549243347
550 34403113846223951177283
551 36270732348871285123699
552 38237961882668817552280
553 40310029416409230738459
554 42492417642119287815331
555 44790905292834514353062
556 47211553717596294448752
557 49760750604354432757376
558 52445195905749110369790
559 55271949286085137652595
560 58248415356964780133230
561 61382395162881764026498
562 64682070749323798042743
563 68156060996536236172174
564 71813405514488757081959
565 75663625229608204067004
566 79716705570469946974064
567 83983162209113588401380
568 88474023578566024051682
569 93200902166643654187580
570 98175976374227529994346
571 103412067875563710992446
572 108922622791483380615942
573 114721795629039707557838
574 120824429837889707704282
575 127246148840550902415900
576 134003336003815833365993
577 141113233412529912746558
578 148593921248731361598508
579 156464424963914190342590
580 164744694173086072489745
581 173455718882380072756766
582 182619507964652877936882
583 192259215272078129196292
584 202399117716258025826487
585 213064752102302039179335
586 224282892976054139084026
587 236081701023305130945921
588 248490700802007932041986
589 261540941761240642258380
590 275264975928258564885198
591 289697032615758293096441
592 304872996304125221835744
593 320830596120295386610807
594 337609384107154893913739
595 355250940815001018707601
596 373798854098188467766388
597 393298942184237178724918
598 413799233346231557406366
599 435350207840317348270000
600 458004778751086720023543
601 481818554503286362923739
602 506849821122762434878552
603 533159827066351502620314
604 560812767396145305800579
605 589876092712500275864594
606 620420495686803284080285
607 652520246268116112057164
608 686253180963801807642895
609 721701066548095513207625
610 758949592792749523848577
611 798088766967999185881914
612 839212910673973898711149
613 882421087896683264554175
614 927817106536770982992601
615 975509982867668990772420
616 1025613948742348410067610
617 1078248955392080004474789
618 1133540687245176769300271
619 1191621108583631746910145
620 1252628484859304366199620
621 1316707975846611128211092
622 1384011665814000195981934
623 1454699206941558065145738
624 1528937859669231886140224
625 1606903190858351526001020
626 1688779125601182954029392
627 1774758704775348784731866
628 1865044150181096531946044
629 1959847686321528964647563
630 2059391620715441260509433
631 2163909235608484556362424
632 2273644885292816989085117
633 2388854963689847316850214
634 2509808021225849618239571
635 2636785814481958737354775
636 2770083445185161435999482
637 2910010499193691779017146
638 3056891210178277361710045
639 3211065695534063596012436
640 3372890148214072283599973
641 3542738177508596708707874
642 3721001032547026259731894
643 3908089057205582486668934
644 4104431948857935592070586
645 4310480337110796081168886
646 4526706082481815237428734
647 4753603989138067267826945
648 4991692148298292069407033
649 5241513796775816318851826
650 5503637710037677552973380
651 5778660218944957323611557
652 6067205658762882193469250
653 6369928557132709817142929
654 6687514145538062692316669
655 7020680733548743500414368
656 7370180289486050938547381
657 7736801016771315178971113
658 8121368012223626849888123
659 8524746061205131302394950
660 8947840382325790664584327
661 9391599660555044587641517
662 9857016887489146130592977
663 10345132652654305648612100
664 10857036090595123020358160
665 11393868451738992843157637
666 11956824168085985343222608
667 12547154728067493595496237
668 13166169873197145290777621
669 13815241802756296534280544
670 14495806516384902537283054
671 15209368375944215482120429
672 15957501609796316972039495
673 16741855262985451980947171
674 17564154879806158717507528
675 18426207875292255015552038
676 19329905415940993589123829
677 20277228247502764885900784
678 21270248794834942208630608
679 22311137485682880433064837
680 23402165091856945834549832
681 24545709591125523990663930
682 25744258775990534152393104
683 27000417698448800353553865
684 28316911574201635086270154
685 29696593860867266773960300
686 31142449487176500286573032
687 32657603618404785998520402
688 34245325245211081667480232
689 35909036693513349075394665
690 37652317609795368848791987
691 39478915279883795756623331
692 41392749049928567117607115
693 43397921522703122950029672
694 45498723459857416192432300
695 47699645928878014105189369
696 50005385735189186330915578
697 52420858601901549459613652
698 54951205183600700930574947
699 57601805366440004355780670
700 60378284923471130875171860
701 63286531028521032840985510
702 66332699616966810798579630
703 69523232218023552371130195
704 72864864089299367429907461
705 76364642479176086117452815
706 80029935613538846525546146
707 83868452507581852160341459
708 87888252888567177716430747
709 92097768690318501305952845
710 96505815001837146522424563
711 101121613386898733783653773
712 105954803960989950390096819
713 111015470688345108146842195
714 116314154696983107083759539
715 121861881722882918261513715
716 127670176780895217514341739
717 133751093937603121196377699
718 140117232471767910600760232
719 146781769170263852819573505
720 153758476121460908346226336
721 161061755750279477364285799
722 168706660398552571224376034
723 176708930330551730975328528
724 185085015274357343128741772
725 193852115645795728075329422
726 203028206237757219811202718
727 212632080937520072186590492
728 222683378765042311087588498
729 233202632378386665341530258
730 244211296687173519314976890
731 255731801462210865864937969
732 267787582767327338869788963
733 280403140023083872114273884
734 293604070518774497281034243
735 307417131305507569810679980
736 321870277081857274186497107
737 336992727319136467569459352
738 352815007836557965050823948
739 369369023603738655757458075
740 386688104345608679310975435
741 404807083499849876761235288
742 423762348231736507110582176
743 443591925059596733749014862
744 464335534689062925109432778
745 486034684872448234756971091
746 508732730503780313494477670
747 532474974319908735604886980
748 557308732748057036074771544
749 583283445101886813105090473
750 610450745711528638394135646
751 638864582333908382360557376
752 668581295136815535720812611
753 699659745096528995443154227
754 732161400470995546082935451
755 766150476015982082122832786
756 801694027632172204927808443
757 838862103313805798709299373
758 877727846708593825419769708
759 918367660781582472526655649
760 960861321106904692456371245
761 1005292153304074193879898920
762 1051747156945130326795512706
763 1100317197924192833381723500
764 1151097143933712394154962227
765 1204186073016036113185083001
766 1259687421663557188567336814
767 1317709210896221493177211633
768 1378364208123907957885388024
769 1441770172223648126550509165
770 1508050030393334089092710154
771 1577332143814679325212943664
772 1649750500854892232588661100
773 1725445005022910006140645612
774 1804561685983565788507354624
775 1887253011677361543335638333
776 1973678118728824767974417158
777 2064003150743253297438398621
778 2158401509851885923373200218
779 2257054223353982965849596934
780 2360150218280478608512935441
781 2467886718753771981897024411
782 2580469545602466498926375362
783 2698113546993629765111844785
784 2821042925334277680080131947
785 2949491703928193307643485518
786 3083704083578657855550072719
787 3223934948277725160271634798
788 3370450254118760395727490592
789 3523527577258167270747277484
790 3683456538002470218836962760
791 3850539394533563993492037146
792 4025091505264693804496853282
793 4207441972141088280732936266
794 4397934144608243625318355362
795 4596926316594863794211385024
796 4804792275760007400354685144
797 5021922058584382849328869242
798 5248722548857213162745697602
799 5485618295704258477069859001
800 5733052165594332345293507064
801 5991486228507162815085352697
802 6261402468147061110426567166
803 6543303741858946450899099795
804 6837714554113255783155939389
805 7145182096283051867483877121
806 7466277088872405774728043268
807 7801594907742985866579055817
808 8151756501072052753173818491
809 8517409609130970421571757565
810 8899229762440099074761188155
811 9297921602834531195851268718
812 9714219969804447262932549929
813 10148891331186113977044055257
814 10602734965324093954092578107
815 11076584510377034212592146129
816 11571309250551968891951057544
817 12087815793808125625662099958
818 12627049471078373600869426921
819 13189996152917647142848870245
820 13777683771442974226526055679
821 14391184287298069419105856949
822 15031615344825452929201128582
823 15700142401714084441377203063
824 16397980528763802215477974390
825 17126396715548837264703950731
826 17886711827163254479243558570
827 18680303100276877491522988120
828 19508606270245503194146237039
829 20373118273183778133458320225
830 21275399557900942473532640316
831 22217077010836498353746354043
832 23199846468577376374301541838
833 24225475883821531493043940748
834 25295808055496971995276740173
835 26412764055483013889288337582
836 27578346194719785785421900582
837 28794641731959718896498793929
838 30063826095886461011830839760
839 31388166898835484452139885750
840 32770027436546372338503958074
841 34211871031752548278772279889
842 35716264834926924666205949454
843 37285884524588217529716056858
844 38923518434451347593010958422
845 40632072639400673501688362753
846 42414575436491388855031013524
847 44274182847997609940243810741
848 46214183485911263337111395374
849 48238004505929214016341873464
850 50349216887676226755714776571
851 52551541876147039010384540097
852 54848856712456910110630950337
853 57245201602333536237114022805
854 59744785934984263799345483646
855 62351995821328289549214665891
856 65071400841813164301778429942
857 67907762200418949875852866531
858 70866040045516561528825668348
859 73951402289532005957331751320
860 77169232550461935052604947667
861 80525139690984365845367519720
862 84024966432322502062338217915
863 87674799670795146675673859587
864 91480979819839556465408655128
865 95450111966823517852557061710
866 99589076003488674761281508702
867 103905038690751751630955470836
868 108405464642948565635990489067
869 113098129373644577851390624831
870 117991131204260859400878147499
871 123092905369958432777073116264
872 128412236928844815560903071614
873 133958276013165067631474547206
874 139740551821713133103288201959
875 145768989108216486623913949628
876 152053923346136426259971157421
877 158606118553696417431847045996
878 165436783727338538287733084827
879 172557592110596595640399593234
880 179980699000537800659899968498
881 187718762576041099642814429720
882 195784963189819274497495090574
883 204193025881123335512830178821
884 212957241274863147828449880090
885 222092489913491293654985524757
886 231614264894849866498719363590
887 241538698168481624527315178361
888 251882585054237182690972235040
889 262663412660090356150591130787
890 273899386434770484831630103970
891 285609460876371100329971140023
892 297813368284942663258083412748
893 310531651944349233813920387587
894 323785697253846699038009275475
895 337597767580427104875211164181
896 351991037962529948002382575487
897 366989633845426981227475641639
898 382618667566085844135279775199
899 398904280200653395819254506495
900 415873681055941613055558157402
901 433555192876539531087228925251
902 451978294586135389058655134880
903 471173670120975657394823185115
904 491173254684108184360944777106
905 512010287492584844397010000522
906 533719361828367573793669519607
907 556336482009740068071399064008
908 579899117544894291232589876333
909 604446264662044938647911012625
910 630018504896577694351235316808
911 656658071540248718776792346785
912 684408913018693965939359057447
913 713316764648893234122598287228
914 743429217191781833757860928936
915 774795794337227765820237531007
916 807468026847580930483059333541
917 841499536221802614331267507951
918 876946114878280190350111685536
919 913865816485680423486405066750
920 952319042668379305317272672411
921 992368640529214594388885554729
922 1034079996399743936673188711867
923 1077521141120571341397398689228
924 1122762851399350300130831626886
925 1169878763459173894661608961241
926 1218945482611100756137775012116
927 1270042705928095150029707279575
928 1323253340687400818403823541084
929 1378663636778122744608506419570
930 1436363314719724088153209224955
931 1496445708567209282029231684782
932 1559007904266909131592496029923
933 1624150893881922958818058316309
934 1691979725106966609636048223047
935 1762603667699924358850150942696
936 1836136375041263081882925636616
937 1912696063727159213943851080855
938 1992405688127622810098555925312
939 2075393134169931709479060559817
940 2161791407925235672917011032598
941 2251738844689892053427982289844
942 2345379312709973388055798585967
943 2442862438754801545567295047061
944 2544343828174555267071291744634
945 2649985308251694352923192034898
946 2759955165881174170088860959206
947 2874428410083806869907819978392
948 2993587028698075260885583235344
949 3117620271547411926979120867462
950 3246724927639709982407544304925
951 3381105630594438285828298284898
952 3520975157963490692824162540588
953 3666554760646647127956344306190
954 3818074486071570591445152045007
955 3975773533460423033024973934762
956 4139900602740467683918978558681
957 4310714277666602413581236593307
958 4488483402480443324979011669297
959 4673487495046245204230531806081
960 4866017153431208074213776483434
961 5066374501379277964399166412722
962 5274873627152072299571386941329
963 5491841063841806580887369053565
964 5717616262994517070512744084293
965 5952552112453464576684381204320
966 6197015447479354408918010938894
967 6451387609023188709970129910797
968 6716064995265853347881651343314
969 6991459663439340397077315347575
970 7277999924934875077233213583469
971 7576130994027952290703815097177
972 7886315629944593146872556356669
973 8209034836103596418044917805430
974 8544788552789120681805100230502
975 8894096410797094823330639609890
976 9257498478644361325163042017562
977 9635556074800288403768986034253
978 10028852573661960546364140543716
979 10437994280872373856676012883756
980 10863611302612984561150900035617
981 11306358488849864682016828098837
982 11766916370845450458577117173077
983 12245992177539511607834487453052
984 12744320846554181566988006033823
985 13262666119314202548127912943473
986 13801821631219556556084459190713
987 14362612091531794232217651763150
988 14945894458823997794086891911032
989 15552559212113915719970799294386
990 16183531618163723362652740614047
991 16839773100833956878604913215477
992 17522282607302973674132806177439
993 18232098083140018916597409679499
994 18970297945054834146654577495750
995 19738002669751617838450919800306
996 20536376381394095928098407289856
997 21366628562913781584556907794729
998 22230015766993672561386454443930
999 23127843459154809289445464079648
1000 24061467861732457437145017272869