1 1
2 2
3 4
4 5
5 8
6 10
7 14
8 18
9 26
10 34
11 46
12 60
13 81
14 105
15 139
16 180
17 236
18 302
19 390
20 495
21 632
22 797
23 1007
24 1260
25 1580
26 1963
27 2441
28 3015
29 3723
30 4570
31 5609
32 6847
33 8355
34 10149
35 12316
36 14889
37 17983
38 21643
39 26021
40 31191
41 37344
42 44589
43 53180
44 63267
45 75181
46 89140
47 105564
48 124760
49 147279
50 173531
51 204232
52 239949
53 281595
54 329937
55 386161
56 451282
57 526829
58 614160
59 715226
60 831826
61 966473
62 1121511
63 1300162
64 1505505
65 1741637
66 2012565
67 2323527
68 2679696
69 3087742
70 3554352
71 4087975
72 4697212
73 5392790
74 6185696
75 7089507
76 8118271
77 9289098
78 10619870
79 12132171
80 13848657
81 15796483
82 18004334
83 20506262
84 23338476
85 26543667
86 30167364
87 34262969
88 38887680
89 44108116
90 49995932
91 56634180
92 64112366
93 72533814
94 82010184
95 92669727
96 104651426
97 118114311
98 133230937
99 150198143
100 169229882
101 190569299
102 214481133
103 241265386
104 271248957
105 304801372
106 342325716
107 384276343
108 431149396
109 483502851
110 541946247
111 607163753
112 679903210
113 761002163
114 851376635
115 952050672
116 1064144458
117 1188908255
118 1327710083
119 1482074150
120 1653668672
121 1844349567
122 2056148058
123 2291320919
124 2552338248
125 2841940507
126 3163127359
127 3519222699
128 3913864302
129 4351078608
130 4835271878
131 5371315408
132 5964539512
133 6620830897
134 7346629520
135 8149040703
136 9035836084
137 10015581688
138 11097645024
139 12292341839
140 13610949903
141 15065878143
142 16670689216
143 18440293328
144 20390982765
145 22540654453
146 24908858017
147 27517052607
148 30388671986
149 33549419505
150 37027355208
151 40853235321
152 45060624590
153 49686288429
154 54770336332
155 60356673288
156 66493182105
157 73232243767
158 80630964777
159 88751778810
160 97662728563
161 107438159474
162 118159068435
163 129913904645
164 142798995938
165 156919475303
166 172389800263
167 189334822587
168 207890420110
169 228204732759
170 250438925123
171 274768617138
172 301384802056
173 330495499621
174 362326859903
175 397125074758
176 435157697838
177 476715857298
178 522115831203
179 571701605663
180 625846753128
181 684957390944
182 749474411789
183 819876908331
184 896684817535
185 980462880438
186 1071823774345
187 1171432692381
188 1280011042276
189 1398341745579
190 1527273599633
191 1667727404101
192 1820701100660
193 1987276856371
194 2168627105477
195 2366022741853
196 2580840212981
197 2814570987599
198 3068829878538
199 3345365983706
200 3646072432133
201 3972999029396
202 4328363658655
203 4714566886091
204 5134205287981
205 5590088317503
206 6085253859268
207 6622987708048
208 7206841706498
209 7840656226145
210 8528581302383
211 9275102575363
212 10085065885775
213 10963707205267
214 11916681236286
215 12950095925903
216 14070545699295
217 15285151248489
218 16601598107922
219 18028182516679
220 19573856161153
221 21248279009375
222 23061871173857
223 25025873760119
224 27152408925623
225 29454549941758
226 31946390696165
227 34643126322527
228 37561133582578
229 40718063627370
230 44132934884263
231 47826239745928
232 51820051838720
233 56138148670955
234 60806135438337
235 65851585970283
236 71304185514927
237 77195892663520
238 83561103925879
239 90436839668825
240 97862933703593
241 105882246722741
242 114540884553046
243 123888443077267
244 133978259344896
245 144867692496453
246 156618412527954
247 169296722391562
248 182973889854034
249 197726516681680
250 213636919820633
251 230793554364689
252 249291451168567
253 269232701252587
254 290726957916120
255 313891991306673
256 338854264248688
257 365749566870791
258 394723676655366
259 425933084409365
260 459545750448684
261 495741934760855
262 534715062908618
263 576672674947177
264 621837416509624
265 670448123060179
266 722760953690381
267 779050629562176
268 839611730366823
269 904760108316369
270 974834369944634
271 1050197489931126
272 1131238503938615
273 1218374349844342
274 1312051800816224
275 1412749565173459
276 1520980492851184
277 1637293969337180
278 1762278433057278
279 1896564103591593
280 2040825852575084
281 2195786311682525
282 2362219145337720
283 2540952590045707
284 2732873183547544
285 2938929793929564
286 3160137867149006
287 3397584011986782
288 3652430836071062
289 3925922161489431
290 4219388528587104
291 4534253126900895
292 4872038056472093
293 5234371069753681
294 5622992691950614
295 6039763882095524
296 6486674127079097
297 6965850144195840
298 7479565078510593
299 8030248384943049
300 8620496275465034
301 9253082936723611
302 9930972392403510
303 10657331232548848
304 11435542077822113
305 12269218019229474
306 13162217895057713
307 14118662665280014
308 15142952738857203
309 16239786535829672
310 17414180133147304
311 18671488299600373
312 20017426762576954
313 21458096037352900
314 23000006655487346
315 24650106150830499
316 26415807633566335
317 28305020340996012
318 30326181989842973
319 32488293351466663
320 34800954869440839
321 37274405776748086
322 39919565527000000
323 42748078035954705
324 45772358543578037
325 49005643635237884
326 52462044228828650
327 56156602112874298
328 60105349839666553
329 64325374609114559
330 68834885946073859
331 73653287861850348
332 78801255302666624
333 84300815636225128
334 90175434980549632
335 96450110192202769
336 103151466321735334
337 110307860425292781
338 117949491546113981
339 126108517833796364
340 134819180623301529
341 144117936527873841
342 154043597379576039
343 164637479165761053
344 175943559810422762
345 188008647052292989
346 200882556287683168
347 214618299743286308
348 229272286871217159
349 244904537455382415
350 261578907351144134
351 279363328483702161
352 298330063062758085
353 318555973788329093
354 340122810048577437
355 363117512048110014
356 387632532919029232
357 413766180933342371
358 441622981929358446
359 471314064268398789
360 502957566506000029
361 536679070310691130
362 572612058898037568
363 610898403751884110
364 651688879997206968
365 695143713458946049
366 741433159884081693
367 790738119649411328
368 843250788562528436
369 899175348396088358
370 958728697912338054
371 1022141228367345371
372 1089657644424399791
373 1161537834849962859
374 1238057794119125094
375 1319510599727473509
376 1406207446561484063
377 1498478743590581090
378 1596675274490756800
379 1701169427975813534
380 1812356499739472959
381 1930656072350465821
382 2056513475336633814
383 2190401332423765140
384 2332821198543892345
385 2484305294265418189
386 2645418340688763710
387 2816759503217942801
388 2998964447736452203
389 3192707518433532835
390 3398704041358160284
391 3617712763867604432
392 3850538434667429195
393 4098034535626594800
394 4361106170762284123
395 4640713124699623524
396 4937873096788191664
397 5253665124416975172
398 5589233202595404497
399 5945790114707874606
400 6324621482504294334
401 6727090051741041935
402 7154640222653942330
403 7608802843339879278
404 8091200276484465590
405 8603551759348655069
406 9147679068859117611
407 9725512513742021738
408 10339097267123947250
409 10990600063775927003
410 11682316277192317789
411 12416677403151190391
412 13196258966925435711
413 14023788883518847353
414 14902156290309948977
415 15834420884488187779
416 16823822787139235553
417 17873792969689876013
418 18987964267331664566
419 20170183018805933668
420 21424521360255636329
421 22755290216580025268
422 24167053021441363970
423 25664640213837714855
424 27253164546230421748
425 28938037257084798159
426 30724985147095051108
427 32620068617410232198
428 34629700713903575943
429 36760667241831527318
430 39020148000237259674
431 41415739207102358387
432 43955477170518116543
433 46647863284229268000
434 49501890409405150724
435 52527070729108240614
436 55733465144636286665
437 59131714309169618654
438 62733071376043079224
439 66549436566966297376
440 70593393646562135519
441 74878248419470886242
442 79418069346443402249
443 84227730407729499790
444 89322956321353645676
445 94720370257893471829
446 100437544171752847613
447 106493051905239118590
448 112906525199196103363
449 119698712782720205963
450 126891542690981418009
451 134508188001572923849
452 142573136155347404238
453 151112262071917313687
454 160152905244553715594
455 169723951046458040974
456 179855916453958267607
457 190581040442651931043
458 201933379285114688638
459 213948907032733069141
460 226665621435831345574
461 240123655613925192090
462 254365395758574199984
463 269435605212954994480
464 285381555241961986296
465 302253162872576636614
466 320103136152993290553
467 338987127249525432558
468 358963893768162876622
469 380095468763120598486
470 402447339861711475169
471 426088638015652413426
472 451092336355096099873
473 477535459708164115602
474 505499305314204629567
475 535069675351607262134
476 566337121865805599684
477 599397204782301852935
478 634350763653787028592
479 671304203896731807241
480 710369798236628238014
481 751666004194993125600
482 795317798414758232189
483 841457028742823649464
484 890222784951928088303
485 941761789114997698064
486 996228806608573411021
487 1053787078862455346522
488 1114608778936426484257
489 1178875491155735802655
490 1246778716001272919674
491 1318520401612270233232
492 1394313503224447816948
493 1474382572040363953141
494 1558964374994977806182
495 1648308547066172438769
496 1742678277747760981196
497 1842351033503159891475
498 1947619317987658064016
499 2058791472042884901572
500 2176192515439287461634
501 2300165032574323995036
502 2431070104309287327885
503 2569288288377098289290
504 2715220650772245313229
505 2869289850802400662054
506 3031941282464413132751
507 3203644275096202070021
508 3384893356244349844350
509 3576209579998154653680
510 3778141924035171537119
511 3991268758958164118309
512 4216199393504640098491
513 4453575699570940947388
514 4704073821002175842072
515 4968405970488126319785
516 5247322318923878793986
517 5541612982013113936143
518 5852110108921301661050
519 6179690078238084808010
520 6525275806549652788125
521 6889839175409542385658
522 7274403582551733377356
523 7680046623716094332563
524 8107902911527474124156
525 8559167038437716736160
526 9035096690829005915211
527 9537015921990240021548
528 10066318591787500106596
529 10624471981512075020741
530 11213020592521695111590
531 11833590138006300416420
532 12487891737367521803662
533 13177726323474524612318
534 13904989273245567335022
535 14671675272840783232485
536 15479883428970761068969
537 16331822638729701493813
538 17229817230617210720609
539 18176312890390861435044
540 19173882885687454484120
541 20225234604409151266231
542 21333216422211708570608
543 22500824915577356165503
544 23731212437346370138365
545 25027695072821279146430
546 26393760995005382968164
547 27833079238879849385697
548 29349508915133986374851
549 30947108885217475101886
550 32630147920163234060910
551 34403115367205050943170
552 36270732348871285128762
553 38237963520943177237564
554 40310029416409244587132
555 42492419404397720872610
556 44790905293907018009141
557 47211555614160398040348
558 49760750604354432757386
559 52445197947746313627417
560 55271949286085137715965
561 58248417552751868050017
562 61382395164161775318506
563 64682073111542943380464
564 68156060996536236172184
565 71813408056839596203580
566 75663625229609055443647
567 79716708303343130521609
568 83983162210640880002331
569 88474026517495817981263
570 93200902166643654187590
571 98175979536033971312398
572 103412067875563710992456
573 108922626189067392956047
574 114721795630860408658501
575 120824433490320564237135
576 127246148840551966562311
577 134003339931725153597483
578 141113233412529912746568
579 148593925468119890197625
580 156464424966082817448070
581 164744698707340387584250
582 173455718882380096095258
583 182619512839056823919897
584 192259215272078129526287
585 202399122950629095580185
586 213064752104884207160139
587 224282898599046831034641
588 236081701023305130945931
589 248490706844586261413868
590 261540941761240642265720
591 275264982414934173206652
592 289697032618827122974982
593 304873003269975366031793
594 320830596120295386610817
595 337609391590065169560945
596 355250940815002702558197
597 373798862128436852709440
598 393298942187883251157054
599 413799241966727832978037
600 435350207840317348270010
601 458004788008144308553632
602 481818554503286362923749
603 506849831053734861481882
604 533159827070679866278997
605 560812778053476538349430
606 589876092712502332463874
607 620420507127059714307362
608 652520246268116112057174
609 686253193233019826880487
610 721701066553229757379490
611 758949605954969709105731
612 798088766967999186006777
613 839212924798226411060805
614 882421087896683264554185
615 927817121679723721849805
616 975509982873756796925514
617 1025613964982134990453304
618 1078248955392080004474799
619 1133540704665979618906672
620 1191621108583631746910155
621 1252628503530795506440919
622 1316707975853817969920571
623 1384011685831426958558889
624 1454699206941558115141686
625 1528937881135168275063385
626 1606903190858354689128381
627 1688779148601189609516739
628 1774758704783877366657999
629 1865044174831202682776546
630 1959847686321528964669505
631 2059391647140527228529489
632 2163909235608484556362434
633 2273644913597837330081146
634 2388854963699932382735992
635 2509808051552031608082545
636 2636785814481962651219085
637 2770083477684418110395131
638 2910010499193691843303024
639 3056891244979232231862484
640 3211065695545980277248750
641 3372890185488482409685029
642 3542738177508596708707884
643 3721001072479541451508407
644 3908089057205582486668944
645 4104431991606013700457120
646 4310480337124871462076958
647 4526706128254173781044308
648 4753603989138067267826955
649 4991692197319220372390554
650 5241513796775816319683710
651 5503637762499727151307105
652 5778660218961559003723590
653 6067205714919484306343551
654 6369928557132709817142939
655 6687514205661440172553660
656 7020680733548749464953887
657 7370180353811425547662149
658 7736801016790889035132294
659 8121368081058512888507067
660 8524746061205131302394960
661 8947840456000332817673707
662 9391599660555044587641527
663 9857016966290401433259602
664 10345132652677367520056686
665 10857036174895938656583305
666 11393868451739000294452949
667 11956824258286445517629495
668 12547154728067493595502065
669 13166169969647255482980393
670 13815241802783448943206170
671 14495806619536377005379428
672 15209368375944215483241998
673 15957501720133631304230783
674 16741855262985451980947181
675 17564154997755650263621510
676 18426207875324210441995146
677 19329905542049511423199346
678 20277228247502764885900794
679 21270248929688765106878035
680 22311137485682880566295790
681 23402165235974892374954312
682 24545709591163085124246511
683 25744258930034131533263402
684 27000417698448800353553875
685 28316911738879831363625430
686 29696593860867277871605331
687 31142449663120060247020405
688 32657603618448918933404668
689 34245325433219728719773430
690 35909036693513349075724705
691 37652317810725762600765193
692 39478915279883795756623341
693 41392749264546866860893426
694 43397921522754943172592805
695 45498723689129703063649460
696 47699645928878027716139279
697 50005385980149860746062173
698 52420858601901549459658540
699 54951205445179608281719082
700 57601805366500810491219010
701 60378285202834474611028669
702 63286531028521032840985520
703 66332699915362724119980704
704 69523232218023552371152330
705 72864864407855341219969835
706 76364642479247406973532364
707 80029935953661656574123584
708 83868452507581852374822608
709 87888253251761884175130193
710 92097768690318501305952855
711 96505815389469697877049944
712 101121613386982294887579680
713 105954804374756131323439207
714 111015470688345108146850300
715 116314155138696524440183815
716 121861881722882938654960152
717 127670177252209281782740531
718 133751093937700984130081295
719 140117232974725477106760262
720 146781769170263852819573515
721 153758476658245881594406603
722 161061755750279477635534772
723 168706660971164630122439127
724 176708930330666271859881577
725 185085015885255746880625885
726 193852115645795752984189391
727 203028206889569986197651325
728 212632080937520072186590502
729 222683379460186024851577411
730 233202632378520643600875155
731 244211297428606706709925527
732 255731801462210865865001535
733 267787583558210323920375887
734 280403140023083872114273894
735 293604071362025285843562680
736 307417131305664218954016437
737 321870277981032622582593583
738 336992727319136467572139105
739 352815008795455957133215662
740 369369023603738655757458085
741 386688105367749941220651385
742 404807083500032850651734069
743 423762349321394151918928491
744 443591925059596733749014872
745 464335535850798483634138290
746 486034684872448271784326306
747 508732731741838107613602765
748 532474974320122372524707641
749 557308734067567635805394648
750 583283445101886813536239885
751 610450747117966916191771819
752 638864582333908382360557386
753 668581296635294279311393910
754 699659745096778286894322797
755 732161402067670820574405240
756 766150476015982127183457383
757 801694029333610862568750961
758 838862103313805798709299383
759 877727848520950325159242668
760 918367660781873199488134945
761 960861323037560814483873090
762 1005292153304074193879898930
763 1051747159001957690209588897
764 1100317197924192833923669763
765 1151097146124113726578727370
766 1204186073016375022219517002
767 1259687423996378387111229160
768 1317709210896221493178043562
769 1378364210608578997366598395
770 1441770172223648126550509175
771 1508050033038752490738311736
772 1577332143815074048889599032
773 1649750503671651735806603904
774 1725445005022910006140645622
775 1804561688982956164492944660
776 1887253011677361609828822390
777 1973678121921532286407950010
778 2064003150743712843868729646
779 2158401513250589964731360503
780 2257054223353982965849642015
781 2360150221898687182164777976
782 2467886718753771981901721680
783 2580469549453004933593920872
784 2698113546994164480174756383
785 2821042929432312216467202080
786 2949491703928193388274450302
787 3083704087940340693022764513
788 3223934948277725160271634808
789 3370450258759473520427114119
790 3523527577258789108163787110
791 3683456542940343404363084610
792 3850539394533563994343413797
793 4025091510519029370421431043
794 4207441972141088280734057880
795 4397934150197476827913759860
796 4596926316595586652827474196
797 4804792281705797515062559753
798 5021922058584382849328869252
799 5248722555182613689484387832
800 5485618295704258477069984060
801 5733052172321422504456911989
802 5991486228508002426815719547
803 6261402475301701333080509497
804 6543303741858946450905285548
805 6837714561722963378455094395
806 7145182096283051986707103615
807 7466277096963606051213804506
808 7801594907743960700949000453
809 8151756509675604512522473577
810 8517409609130970421571757575
811 8899229771588828461969917972
812 9297921602834531195851268728
813 9714219979529959777862768275
814 10148891331187245215547993874
815 10602734975663191221223594165
816 11076584510377034355391142074
817 11571309261543787320061392689
818 12087815793808125625662163717
819 12627049482760689878061744711
820 13189996152918959195978870040
821 13777683783859651786576215692
822 14391184287298069419105856959
823 15031615358023124634594092734
824 15700142401714084441377203073
825 16397980542787591098996821760
826 17126396715550358417594267031
827 17886711842065410771034749989
828 18680303100276877491522988130
829 19508606286081561360311437684
830 20373118273183778133458320235
831 21275399574724765449983360013
832 22217077010838260632179411323
833 23199846486451169343993151132
834 24225475883821531494697782932
835 25295808074486832813101046435
836 26412764055483014097178757699
837 27578346214889968804237171496
838 28794641731961759722351371993
839 30063826117310982372086476090
840 31388166898835484452139885760
841 32770027459303858556350798610
842 34211871031752548278772284463
843 35716264859093977687647313425
844 37285884524590579748861394580
845 38923518460115987806848673280
846 40632072639400673752129300334
847 42414575463747094337180792109
848 44274182847997609942310578608
849 46214183514849300594196193742
850 48238004505931946889525421010
851 50349216918401212177548479685
852 52551541876147039010384562997
853 54848856745079917639394818833
854 57245201602333536237114022815
855 59744785969613964515539259115
856 62351995821331449988466091722
857 65071400878573831543609957277
858 67907762200418949875852866541
859 70866040084540107092698343106
860 73951402289532005957331751330
861 77169232591877674590168543287
862 80525139690988018278755885215
863 84024966476277979232856334459
864 87674799670795146675673859597
865 91480979866491345649258758105
866 95450111966823518214883921620
867 99589076052990565170686659427
868 103905038690755971019484297586
869 108405464695475636367939373605
870 113098129373644577851404473545
871 117991131259998859170817958849
872 123092905369958432777075796062
873 128412236987976529870072690285
874 133958276013169939669531019326
875 139740551884446204479331411010
876 145768989108216487062234772861
877 152053923412691097170490155933
878 158606118553696417431847046006
879 165436783797931931934295220347
880 172557592110602218633091543850
881 179980699075416049556058362850
882 187718762576041099642814429730
883 195784963269243383580949581171
884 204193025881123335512830178831
885 212957241359090878236182734455
886 222092489913497780851227603396
887 231614264984172822820073009267
888 241538698168481624527315178371
889 251882585148964518765460484684
890 262663412660090356154504995105
891 273899386535208029575034561347
892 285609460876378579895067651933
893 297813368391435715163322531341
894 310531651944349233813920512839
895 323785697366761254448562966685
896 337597767580427105501057917316
897 351991038082228660789452118420
898 366989633845435601723754690845
899 382618667692977386826261193209
900 398904280200653395819254517910
901 415873681190459054784114365440
902 433555192876539531087229255487
903 451978294728708525214023001735
904 471173670120985588372050798009
905 491173254835220446432862090810
906 512010287492584845146484412318
907 533719361988531136324395159465
908 556336482009740068071399064018
909 579899117714618242279047917310
910 604446264662056374189988834765
911 630018505076433611630379753817
912 656658071540248718776792346795
913 684408913209287275550344075023
914 713316764648893234122621625761
915 743429217393715213042975617575
916 774795794337240928934816284909
917 807468027061529837515792402685
918 841499536221802614337232047478
919 876946115104959930393838357581
920 913865816485680423486405066760
921 952319042908502961911588247818
922 992368640529229737341624411934
923 1034079996654109332431762911852
924 1077521141120571341397403386542
925 1122762851668802145076610697785
926 1169878763459173895733432737538
927 1218945482896482311379736998413
928 1270042705928112564209840426906
929 1323253340989653981276400185816
930 1378663636778122744608506419580
931 1436363315039845896899358328043
932 1496445708567209282036578487813
933 1559007904605896258842021462484
934 1624150893881942976244820893265
935 1691979725465930503404211099670
936 1762603667699924360130192603247
937 1836136375421380008668856717542
938 1912696063727159213943851080865
939 1992405688530070149968413761606
940 2075393134169954709485716047165
941 2161791408351324312330912522457
942 2251738844689892053427982289854
943 2345379313161090374436414551568
944 2442862438754801545567295092907
945 2544343828652090726779455860445
946 2649985308251720770267133439321
947 2759955166386673475403099789419
948 2874428410083806869907819978402
949 2993587029233173241168779714742
950 3117620271547411926979127053260
951 3246724928206047105940972859516
952 3381105630594468612010288127873
953 3520975158562887897616477410556
954 3666554760646647127956344306200
955 3818074486705953843294627812045
956 3975773533460423034845675035429
957 4139900603411771887815710365925
958 4310714277666637214536144927339
959 4488483403190813123215639907312
960 4673487495046245204241629451120
961 4866017154182911354694265206423
962 5066374501379277964399166419573
963 5274873627947390097986152243715
964 5491841063841846500452896053592
965 5717616263835974099255567733760
966 5952552112453464578853008309804
967 6197015448369619941842104648904
968 6451387609023188709970129910807
969 6716064996207615136996693074312
970 6991459663439386169435859778920
971 7277999925931103886207676505439
972 7576130994027952290703815097187
973 7886315630998429231248733036429
974 8209034836103596418058528755348
975 8544788553903729460741526714760
976 8894096410797147287955714755092
977 9257498479823236816318777820426
978 9635556074800288403768986034263
979 10028852574908795418824727341756
980 10437994280872373856676062879745
981 10863611303931504965592652844888
982 11306358488849924787366667765417
983 11766916372239763961801564990026
984 12245992177539511607834487453062
985 12744320848028628464246059627700
986 13262666119314202551196742822018
987 13801821632778520931079437719562
988 14362612091531863067120268402238
989 14945894460472306341153073892027
990 15552559212113915719970799358910
991 16183531619906475296861224625037
992 16839773100833956878604913215487
993 17522282609145324707635966077032
994 18232098083140097717852712346125
995 18970297947002453464660671156000
996 19738002669751617842096992232446
997 20536376383452971700767593594031
998 21366628562913781584556907794739
999 22230015769169865076825741905565
1000 23127843459154899464880444632260