3 3
4 128
5 1062
6 5160
7 18591
8 55113
9 142005
10 329045
11 701160
12 1395975
13 2626953
14 4713723
15 8120322
16 13503350
17 21770766
18 34153758
19 52292385
20 78337890
21 115072320
22 166048850
23 235753353
24 329791143
25 455099307
26 620189115
27 835418766
28 1113301553
29 1468849515
30 1919958285
31 2487832980
32 3197461500
33 4078134828
34 5164021388
35 6494794767
36 8116322580
37 10081415466
38 12450644748
39 15293227395
40 18687987605
41 22724393265
42 27503677425
43 33140042628
44 39761959083
45 47513554077
46 56556104495
47 67069629366
48 79254595218
49 93333730650
50 109553963850
51 128188478925
52 149538905750
53 173937638628
54 201750299478
55 233378340237
56 269261801235
57 309882219591
58 355765705463
59 407486179530
60 465668790645
61 530993506335
62 604198896225
63 686086100328
64 777523003448
65 879448606872
66 992877619800
67 1118905260891
68 1258712293608
69 1413570284910
70 1584847112240
71 1774012707495
72 1982645064225
73 2212436495853
74 2465200172493
75 2742876923232
76 3047542332815
77 3381414118641
78 3746859818403
79 4146404773290
80 4582740438510
81 5058733005030
82 5577432365750
83 6142081408953
84 6756125673738
85 7423223349192
86 8147255653530
87 8932337573841
88 9782829004223
89 10703346261795
90 11698774019955
91 12774277637190
92 13935315922425
93 15187654314003
94 16537378514933
95 17990908560252
96 19555013360820
97 21236825698116
98 23043857716068
99 24984016883175
100 27065622472700
101 29297422532850
102 31688611396500
103 34248847701003
104 36988272969453
105 39917530722537
106 43047786174185
107 46390746478716
108 49958681584563
109 53764445660805
110 57821499153495
111 62143931436510
112 66746484115850
113 71644574950578
114 76854322451298
115 82392571117797
116 88276917378750
117 94525736193516
118 101158208380958
119 108194348633685
120 115655034284715
121 123562034783295
122 131938041948975
123 140806700958978
124 150192642140093
125 160121513518407
126 170620014200265
127 181715928536016
128 193438161142128
129 205816772731440
130 218883016829360
131 232669377323955
132 247209606930000
133 262538766513078
134 278693265356088
135 295710902312367
136 313630907930105
137 332493987490341
138 352342365045573
139 373219828399320
140 395171775116055
141 418245259499865
142 442489040633675
143 467953631415378
144 494691348685158
145 522756364378302
146 552204757800270
147 583094568956241
148 615485853034418
149 649440735973200
150 685023471214050
151 722300497568025
152 761340498300375
153 802214461359003
154 844995740853803
155 889760119710462
156 936585873608385
157 985553836124091
158 1036747465192413
159 1090252910804580
160 1146159084058220
161 1204557727476060
162 1265543486711100
163 1329213983552703
164 1395669890354148
165 1465015005793722
166 1537356332092700
167 1612804153599891
168 1691472116868933
169 1773477312135585
170 1858940356324065
171 1947985477487220
172 2040740600812475
173 2137337436095853
174 2237911566818943
175 2342602540728582
176 2451553962057090
177 2564913585280266
178 2682833410553978
179 2805469780723965
180 2932983480052710
181 3065539834555380
182 3203308814091750
183 3346465136103453
184 3495188371146563
185 3649663050106167
186 3810078773246055
187 3976630320977466
188 4149517766503173
189 4328946590218095
190 4515127796025905
191 4708278029450040
192 4908619697701800
193 5116381091581128
194 5331796509376008
195 5555106382633227
196 5786557403969720
197 6026402656794366
198 6274901747112768
199 6532320937281975
200 6798933281891025
201 7075018765631325
202 7360864443336125
203 7656764582050128
204 7963020805311903
205 8279942239507137
206 8607845662478835
207 8947055654249466
208 9297904750044638
209 9660733595470230
210 10035891104036070
211 10423734616874985
212 10824630064853850
213 11238952132922328
214 11667084426899498
215 12109419642540897
216 12566359737089775
217 13038316103151891
218 13525709745101283
219 14028971457853110
220 14548542008214665
221 15084872318647395
222 15638423653654725
223 16209667808625228
224 16799087301349668
225 17407175566038132
226 18034437150059540
227 18681387913226391
228 19348555229850828
229 20036478193391490
230 20745707823921060
231 21476807278230555
232 22230352062804125
233 23006930249476953
234 23807142694013913
235 24631603257418092
236 25480939030210755
237 26355790559488341
238 27256812079002023
239 28184671742061870
240 29140051857515130
241 30123649128597090
242 31136174894908050
243 32178355377311253
244 33250931926009358
245 34354661271590652
246 35490315779306670
247 36658683706368741
248 37860569462529243
249 39096793873731375
250 40368194449097375
251 41675625651035250
252 43019959168738125
253 44402084194852503
254 45822907705593753
255 47283354744081312
256 48784368707176160
257 50326911635589216
258 51911964507547488
259 53540527535782755
260 55213620468133920
261 56932282891523910
262 58697574539606600
263 60510575603840703
264 62372387048290473
265 64284130927906197
266 66246950710588725
267 68262011602787016
268 70330500878937383
269 72453628214489385
270 74632626022831515
271 76868749795857570
272 79163278448491350
273 81517514666906478
274 83932785260763518
275 86410441519197057
276 88951859570879490
277 91558440747890016
278 94231611953720178
279 96972826035140265
280 99783562158262535
281 102665326188521355
282 105619651074910875
283 108648097238196078
284 111752252963442513
285 114933734796576267
286 118194187945324205
287 121535286684241716
288 124958734764182748
289 128466265825915020
290 132059643818239980
291 135740663420316015
292 139511150468549300
293 143372962387746378
294 147327988626897708
295 151378151099281827
296 155525404627264245
297 159771737391476241
298 164119171384752593
299 168569762870508900
300 173125602845942475
301 177788817509732925
302 182561568734631375
303 187446054544609878
304 192444509596964978
305 197559205669042362
306 202792452149981610
307 208146596537143341
308 213624024937622838
309 219227162574507780
310 224958474298289270
311 230820465103079085
312 236815680648047475
313 242946707783729703
314 249216175083620823
315 255626753380702122
316 262181156309323925
317 268882140852083391
318 275732507892127233
319 282735102770513160
320 289892815849065240
321 297208583078352120
322 304685386571228600
323 312326255181564603
324 320134265088607368
325 328112540386595982
326 336264253680079440
327 344592626684552391
328 353100930832865153
329 361792487887017165
330 370670670555795885
331 379738903117865280
332 389000662050771375
333 398459476665463953
334 408118929746807363
335 417982658199674442
336 428054353701102030
337 438337763358096966
338 448836690371576598
339 459554994706027545
340 470496593765372330
341 481665463074622440
342 493065636967813050
343 504701209281792753
344 516576334056369183
345 528695226240378627
346 541062162404186195
347 553681481458179366
348 566557585377767193
349 579694939934442675
350 593098075433426325
351 606771587457443100
352 620720137617156500
353 634948454307806628
354 649461333472581828
355 664263639372265287
356 679360305361692060
357 694756334672552466
358 710456801203083188
359 726466850314176555
360 742791699632455245
361 759436639859837385
362 776407035590145225
363 793708326132276828
364 811346026340499923
365 829325727451381797
366 847653097927920375
367 866333884310384766
368 885373912074436458
369 904779086496033810
370 924555393523697090
371 944708900657631045
372 965245757836288350
373 986172198329865228
374 1007494539641318718
375 1029219184414391157
376 1051352621349237515
377 1073901426125135391
378 1096872262330879503
379 1120271882402334690
380 1144107128567755485
381 1168384933800340455
382 1193112322778635625
383 1218296412854249328
384 1243944415027499088
385 1270063634930446992
386 1296661473817950480
387 1323745429566179091
388 1351323097679230448
389 1379402172303290070
390 1407990447248974680
391 1437095817021297615
392 1466726277857902425
393 1496889928774997253
394 1527594972621642533
395 1558849717141818552
396 1590662576044931895
397 1623042070084181241
398 1655996828143448043
399 1689535588332126450
400 1723667199088564550
401 1758400620291525150
402 1793744924380344750
403 1829709297483192753
404 1866303040554116178
405 1903535570518265712
406 1941416421425995010
407 1979955245615222841
408 2019161814882756663
409 2059046021663960955
410 2099617880221475595
411 2140887527842361310
412 2182865226044384225
413 2225561361790810203
414 2268986448714427773
415 2313151128350163972
416 2358066171377018700
417 2403742478868675516
418 2450191083553521308
419 2497423151083426335
420 2545449981312023940
421 2594283009581834970
422 2643933808020983100
423 2694414086848839603
424 2745735695691350693
425 2797910624905379457
426 2850951006912822465
427 2904869117543826516
428 2959677377389872603
429 3015388353166045965
430 3072014759083266335
431 3129569458229790630
432 3188065463962769250
433 3247515941309161578
434 3307934208376798938
435 3369333737774893917
436 3431728158044791430
437 3495131255100253716
438 3559556973678081798
439 3625019418798358845
440 3691532857235125155
441 3759111718996763415
442 3827770598816911175
443 3897524257655172378
444 3968387624208452133
445 4040375796432179727
446 4113504043072251345
447 4187787805206950616
448 4263242697799685768
449 4339884511261794600
450 4417729213026263400
451 4496792949131604075
452 4577092045816743000
453 4658643011126158878
454 4741462536526130528
455 4825567498531324887
456 4910974960342593585
457 4997702173495201341
458 5085766579518362013
459 5175185811605298480
460 5265977696294709695
461 5358160255162853985
462 5451751706527139475
463 5546770467160423578
464 5643235154016919998
465 5741164585968908022
466 5840577785555150150
467 5941493980740205641
468 6043932606685553658
469 6147913307531706360
470 6253455938192233290
471 6360580566158870145
472 6469307473318640975
473 6579657157782159603
474 6691650335724047043
475 6805307943234623382
476 6920651138183818665
477 7037701302096453891
478 7156480042039844453
479 7277009192522869740
480 7399310817407469060
481 7523407211831700180
482 7649320904145328500
483 7777074657857075703
484 7906691473594503788
485 8038194591075655842
486 8171607491093437380
487 8306953897511852091
488 8444257779275083773
489 8583543352428530745
490 8724835082152792505
491 8868157684809707340
492 9013536130001448675
493 9160995642641771253
494 9310561705040422983
495 9462260058999805902
496 9616116707924910170
497 9772157918945596866
498 9930410225052261618
499 10090900427243947125
500 10253655596689944750
501 10418703076903945500
502 10586070485931788750
503 10755785718551861253
504 10927876948489203003
505 11102372630642364687
506 11279301503324081535
507 11458692590514800466
508 11640575204130133613
509 11824978946301267255
510 12011933711669407545
511 12201469689693284160
512 12393617366970801600
513 12588407529573851328
514 12785871265397382848
515 12986039966521738947
516 13188945331589361600
517 13394619368194865766
518 13603094395289596008
519 13814403045599655135
520 14028578268058528265
521 14245653330253283445
522 14465661820885480725
523 14688637652245762728
524 14914615062703267143
525 15143628619208826057
526 15375713219813101115
527 15610904096198611266
528 15849236816226810678
529 16090747286499165390
530 16335471754933394910
531 16583446813353819105
532 16834709400096985250
533 17089296802631507328
534 17347246660193301138
535 17608596966435139017
536 17873386072091716455
537 18141652687659146091
538 18413435886090080123
539 18688775105503368270
540 18967710151909461105
541 19250281201950457515
542 19536528805656014925
543 19826493889214012628
544 20120217757757195708
545 20417742098164681452
546 20719108981879564620
547 21024360867741494991
548 21333540604835472468
549 21646691435355724650
550 21963856997485921100
551 22285081328294580675
552 22610408866646935125
553 22939884456132096753
554 23273553348006802353
555 23611461204154572612
556 23953654100061568235
557 24300178527807973341
558 24651081399076196463
559 25006410048174711030
560 25366212235078834770
561 25730536148487261210
562 26099430408895651850
563 26472944071686093453
564 26851126630233738198
565 27234028019029422372
566 27621698616819590550
567 28014189249762312141
568 28411551194600726483
569 28813836181852694535
570 29221096399018002615
571 29633384493801887370
572 30050753577356236725
573 30473257227537227103
574 30900949492180760993
575 31333884892394456232
576 31772118425867560440
577 32215705570197533016
578 32664702286234677528
579 33119165021443557915
580 33579150713282590760
581 34044716792600538030
582 34515921187051302000
583 34992822324525737703
584 35475479136601894113
585 35963951062012390317
586 36458298050130347405
587 36958580564472573216
588 37464859586221430223
589 37977196617764074545
590 38495653686250505955
591 39020293347169107690
592 39551178687941125550
593 40088373331532755878
594 40631941440086301558
595 41181947718569056377
596 41738457418441386570
597 42301536341342660616
598 42871250842796505818
599 43447667835934033425
600 44030854795236520575
601 44620879760296181475
602 45217811339596525875
603 45821718714310927878
604 46432671642120912953
605 47050740461052776787
606 47675996093334053685
607 48308510049268438716
608 48948354431130691188
609 49595601937080114180
610 50250325865094147620
611 50912600116920660135
612 51582499202050487100
613 52260098241708790578
614 52945472972866798548
615 53638699752272489547
616 54339855560501790125
617 55049018006028841641
618 55766265329316913833
619 56491676406928512060
620 57225330755656265715
621 57967308536673135045
622 58717690559703533975
623 59476558287213896478
624 60243993838624294218
625 61020079994539623282
626 61804900201001977890
627 62598538573762719141
628 63401079902575866878
629 64212609655511312940
630 65033213983289494110
631 65862979723636013205
632 66701994405657856875
633 67550346254239688703
634 68408124194461876463
635 69275417856038722242
636 70152317577778564605
637 71038914412064211591
638 71935300129355384073
639 72841567222711618320
640 73757808912337317680
641 74684119150147392240
642 75620592624355186800
643 76567324764081126003
644 77524411743983787408
645 78491950488911821302
646 79470038678578438520
647 80458774752256874991
648 81458257913498564793
649 82468588134872420325
650 83489866162726961925
651 84522193521973685400
652 85565672520893420375
653 86620406255964057753
654 87686498616711409803
655 88764054290581570962
656 89853178767836553510
657 90953978346471555966
658 92066560137155649038
659 93191032068194226705
660 94327502890515017970
661 95476082182675996560
662 96636880355896994850
663 97810008659113348953
664 98995579184053392023
665 100193704870338112347
666 101404499510604804075
667 102628077755653016766
668 103864555119614642433
669 105114047985146435835
670 106376673608646817565
671 107652550125495245220
672 108941796555316013100
673 110244532807264755228
674 111560879685339523068
675 112890958893714702207
676 114234893042099650340
677 115592805651120310266
678 116964821157725691228
679 118351064920617461715
680 119751663225704558085
681 121166743291581041505
682 122596433275029118625
683 124040862276545547828
684 125500160345893357563
685 126974458487677087917
686 128463888666943493055
687 129968583814805904966
688 131488677834094207298
689 133024305605028608970
690 134575602990919177530
691 136142706843889311165
692 137725755010625120550
693 139324886338148888628
694 140940240679618590758
695 142571958900151632477
696 144220182882674798595
697 145885055533798559991
698 147566720789717743143
699 149265323622136697850
700 150981010044220979525
701 152713927116573670575
702 154464222953238368625
703 156232046727726955128
704 158017548679074183528
705 159820880117917189512
706 161642193432601973960
707 163481642095314950091
708 165339380668241616888
709 167215564809750439230
710 169110351280604008320
711 171023897950195551735
712 172956363802812878225
713 174907908943927815453
714 176878694606513237373
715 178868883157385728272
716 180878638103575991775
717 182908124098725040641
718 184957506949508287283
719 187026953622085559610
720 189116632248579173790
721 191226712133578077270
722 193357363760670205350
723 195508758799001053353
724 197681070109860619418
725 199874471753296708632
726 202089138994756765290
727 204325248311756212641
728 206582977400575478703
729 208862505182983676115
730 211164011812991126435
731 213487678683628685430
732 215833688433756071625
733 218202224954897143203
734 220593473398104337413
735 223007620180850206092
736 225444852993948273380
737 227905360808501137716
738 230389333882878056148
739 232896963769719921495
740 235428443322973882380
741 237983966704955505090
742 240563729393440739300
743 243167928188785575003
744 245796761221075664733
745 248450427957303786777
746 251129129208577435545
747 253833067137354403116
748 256562445264708650243
749 259317468477624319125
750 262098343036320198375
751 264905276581602480750
752 267738478142248136250
753 270598158142416729378
754 273484528409093015378
755 276397802179558132437
756 279338194108891736910
757 282305920277502886716
758 285301198198692032238
759 288324246826241908005
760 291375286562039696795
761 294454539263728247535
762 297562228252388730975
763 300698578320252502578
764 303863815738444568973
765 307058168264756415447
766 310281865151450603225
767 313535137153094882016
768 316818216534428239008
769 320131337078256617760
770 323474734093380740640
771 326848644422553756195
772 330253306450471157600
773 333688960111790681478
774 337155846899184645768
775 340654209871422423807
776 344184293661485525865
777 347746344484712973141
778 351340610146979448053
779 354967340052903893640
780 358626785214091058535
781 362319198257403648105
782 366044833433267590875
783 369803946624008068578
784 373596795352218831638
785 377423638789162436142
786 381284737763203936830
787 385180354768275659841
788 389110753972375602498
789 393076201226097071520
790 397076964071192119730
791 401113311749166380265
792 405185515209907871175
793 409293847120347357003
794 413438581873152853083
795 417619995595455846702
796 421838366157611833745
797 426093973181992732491
798 430387098051813786093
799 434718023919992502900
800 439087035718042259100
801 443494420164998100300
802 447940465776377379500
803 452425462873172755503
804 456949703590880202228
805 461513481888559540362
806 466117093557930154860
807 470760836232499397091
808 475445009396726348213
809 480169914395218429905
810 484935854441963552145
811 489743134629595271460
812 494592061938693662475
813 499482945247119363453
814 504416095339383511823
815 509391824916051017622
816 514410448603179904050
817 519472282961794150266
818 524577646497392778858
819 529726859669492610285
820 534920244901207439990
821 540158126588861047620
822 545440831111636807350
823 550768686841261295853
824 556142024151724680243
825 561561175429035269607
826 567026475081011025815
827 572538259547105404266
828 578096867308270333653
829 583702638896853692415
830 589355916906534104385
831 595057046002290398280
832 600806372930408567000
833 606604246528523558328
834 612451017735698746488
835 618347039602540403067
836 624292667301350030280
837 630288258136311861966
838 636334171553718408848
839 642430769152231340295
840 648578414693180592705
841 654777474110898983565
842 661028315523095234925
843 667331309241262672128
844 673686827781126515183
845 680095245873127015377
846 686556940472941368195
847 693072290772041641866
848 699641678208291666318
849 706265486476580108550
850 712944101539492692950
851 719677911638020779225
852 726467307302309270250
853 733312681362441049128
854 740214428959260931578
855 747172947555236319537
856 754188636945357555935
857 761261899268075153091
858 768393139016276908563
859 775582763048302067430
860 782831180598995558745
861 790138803290799451635
862 797506045144884672725
863 804933322592320116828
864 812421054485282206548
865 819969662108302019172
866 827579569189553050500
867 835251201912176720391
868 842984988925648703708
869 850781361357183177810
870 858640752823178084340
871 866563599440698482795
872 874550339839001107725
873 882601415171097193353
874 890717269125356691593
875 898898347937150933532
876 907145100400536874515
877 915457977879979959141
878 923837434322118760503
879 932283926267568416190
880 940797912862766029610
881 949379855871855045330
882 958030219688611781250
883 966749471348411112453
884 975538080540234503838
885 984396519618717372492
886 993325263616238991230
887 1002324790255051900341
888 1011395579959454053323
889 1020538115868000649695
890 1029752883845758895055
891 1039040372496602627490
892 1048401073175550064925
893 1057835480001141598503
894 1067344089867860901033
895 1076927402458596261552
896 1086585920257145429520
897 1096320148560760865616
898 1106130595492738697168
899 1116017772015048261075
900 1125982191941005546800
901 1136024371947987408150
902 1146144831590189871000
903 1156344093311427391503
904 1166622682457976406553
905 1176981127291460016837
906 1187419959001777158885
907 1197939711720073092216
908 1208540922531754572663
909 1219224131489546523705
910 1229989881626593591595
911 1240838718969603381810
912 1251771192552034777350
913 1262787854427328122078
914 1273889259682180684398
915 1285075966449864170097
916 1296348535923587714450
917 1307707532369903108016
918 1319153523142155701058
919 1330687078693977726585
920 1342308772592827501815
921 1354019181533571233595
922 1365818885352110902475
923 1377708467039054936478
924 1389688512753435164193
925 1401759611836466743707
926 1413922356825354571965
927 1426177343467142856516
928 1438525170732611369228
929 1450966440830215049340
930 1463501759220070490460
931 1476131734627985964255
932 1488856979059538530500
933 1501678107814194871578
934 1514595739499479416188
935 1527610496045186375667
936 1540723002717639272805
937 1553933888133994571841
938 1567243784276593004673
939 1580653326507355187220
940 1594163153582225136155
941 1607773907665658265165
942 1621486234345157486175
943 1635300782645853979878
944 1649218205045136276258
945 1663239157487324194602
946 1677364299398391298970
947 1691594293700732403741
948 1705929806827979800518
949 1720371508739864726100
950 1734920072937127758150
951 1749576176476474643325
952 1764340499985581259875
953 1779213727678144204503
954 1794196547368980720903
955 1809289650489174444762
956 1824493732101270698085
957 1839809490914517792591
958 1855237629300158090513
959 1870778853306765267480
960 1886433872675631541320
961 1902203400856201296360
962 1918088155021554882600
963 1934088856083939004203
964 1950206228710347492248
965 1966441001338148861022
966 1982793906190764458400
967 1999265679293393594391
968 2015857060488789474033
969 2032568793453082303485
970 2049401625711653411165
971 2066356308655056737520
972 2083433597554991550975
973 2100634251580322728353
974 2117959033813152473043
975 2135408711264939793882
976 2152984054892671633790
977 2170685839615081955766
978 2188514844328922691078
979 2206471851925282841865
980 2224557649305959658810
981 2242773027399878170680
982 2261118781179563002250
983 2279595709677658741953
984 2298204616003502811663
985 2316946307359747084467
986 2335821595059032218755
987 2354831294540710938966
988 2373976225387624247273
989 2393257211342926780995
990 2412675080326965316005
991 2432230664454206615340
992 2451924800050218639300
993 2471758327668701300628
994 2491732092108570797108
995 2511846942431093689527
996 2532103731977074773420
997 2552503318384094896866
998 2573046563603802788868
999 2593734333919257034875
1000 2614567499962322280125