0 0
1 1
2 36
3 834
4 8230
5 48915
6 210126
7 720916
8 2097684
9 5381685
10 12501280
11 26796726
12 53750346
13 101969959
14 184478490
15 320367720
16 536879176
17 871980201
18 1377508284
19 2122961770
20 3200020110
21 4727881851
22 6859513606
23 9788908284
24 13759455900
25 19073535325
26 26103440376
27 35303758686
28 47225326834
29 62530890255
30 82012601490
31 106611495376
32 137439084816
33 175801225809
34 223224405460
35 281484611730
36 352638948726
37 439060166371
38 543474278334
39 669001447140
40 819200320420
41 998116007301
42 1210331888976
43 1461025462534
44 1756028422170
45 2101891186935
46 2505952089226
47 2976411443256
48 3522410717784
49 4154117042425
50 4882813281900
51 5720993917626
52 6682466981086
53 7782462288459
54 9037746231030
55 10466743380940
56 12089665176876
57 13928645959341
58 16007886630184
59 18353806216110
60 20995201620930
61 23963415856351
62 27292515046146
63 31019474503584
64 35184374187040
65 39830603843745
66 45005078156676
67 50758462214626
68 57145407630534
69 64224799638195
70 72060015502510
71 80719194583476
72 90275520399156
73 100807515037909
74 112399346275200
75 125141147755350
76 139129352603626
77 154467040839111
78 171264300963834
79 189638606108680
80 209715205121640
81 231627528989001
82 255517612985116
83 281536534951434
84 309844870110510
85 340613162825755
86 374022415722726
87 410264596592796
88 449543163505084
89 492073608557565
90 538084020703320
91 587815668092926
92 641523600379026
93 699477271434159
94 761961182937970
95 829275549294960
96 901736984348976
97 979679210365681
98 1063453789759284
99 1153430880044850
100 1250000012502550
101 1353570895045251
102 1464574239785886
103 1583462615806084
104 1710711327632580
105 1846819319932965
106 1992310108947376
107 2147732741177766
108 2313662779861434
109 2490703319760535
110 2679486030804330
111 2880672231125976
112 3094953990040696
113 3323055261517209
114 3565733048699340
115 3823778600039770
116 4098018637612926
117 4389316618179051
118 4698574027576534
119 5026731709024620
120 5374771225923660
121 5743716259745101
122 6134634043608456
123 6548636832147534
124 6986883408273250
125 7450580627445375
126 7940985000070626
127 8459404312649536
128 9007199288299584
129 9585785287287105
130 10196634048205540
131 10841275470442626
132 11521299438584166
133 12238357689407059
134 12994165722119310
135 13790504752509780
136 14629223711675476
137 15512241289999221
138 16441548027055584
139 17419208448127990
140 18447363248024970
141 19528231522888551
142 20664113050692826
143 21857390621135784
144 23110532415632520
145 24426094438122985
146 25806722997412476
147 27255157241768106
148 28774231746499534
149 30366879155257275
150 32036132875786950
151 33785129830882876
152 35617113265289436
153 37535435609303709
154 39543561399837880
155 41645070259704990
156 43843659935896626
157 46143149397626191
158 48547481994916434
159 51060728678514960
160 53687091281926480
161 56430905866355601
162 59296646129358996
163 62288926878010834
164 65412507567390390
165 68672295905205795
166 72073351523372926
167 75620889717373476
168 79320285254221284
169 83177076249871045
170 87196968116908560
171 91385837583366726
172 95749736783516506
173 100294897421487159
174 105027735008575050
175 109954853175105400
176 115083048057716376
177 120419312762939961
178 125970841907959084
179 131745036239425530
180 137749507331228190
181 143992082362106251
182 150480808974006966
183 157223960212092684
184 164230039547306860
185 171507785982413805
186 179066179242431976
187 186914445050385646
188 195062060489304834
189 203518759451408415
190 212294538175410370
191 221399660872894176
192 230844665444705376
193 240640369288317409
194 250797875197130820
195 261328577352671010
196 272244167410654726
197 283556640681900531
198 295278302409063534
199 307421774140179700
200 320000000200010100
201 333026254260180501
202 346514146009116736
203 360477627922781334
204 374931002137221930
205 389888927423947015
206 405366426269149626
207 421378892057804616
208 437942096363670184
209 455072196346229385
210 472785742255612380
211 491099685046545226
212 510031384102376046
213 529598615070234459
214 549819577808385190
215 570712904446841820
216 592297667562311676
217 614593388468547901
218 637620045623189784
219 661398083152177470
220 685948419492832210
221 711292456156698351
222 737452086613248306
223 764449705295556784
224 792308216729055600
225 821051044784485425
226 850702142056165876
227 881285999366710386
228 912827655399317334
229 945352706458773955
230 978887316362314590
231 1013458226461479876
232 1049092765796128516
233 1085818861381758309
234 1123665048631298160
235 1162660481912537830
236 1202834945242367226
237 1244218863119002071
238 1286843311493377834
239 1330740028880898840
240 1375941427614734520
241 1422480605241859801
242 1470391356063041676
243 1519708182817979034
244 1570466308516807870
245 1622701688419189035
246 1676451022162200726
247 1731751766038262956
248 1788642145424326284
249 1847161167363562125
250 1907348633300797000
251 1969245151972938126
252 2032892152455642786
253 2098331897367488959
254 2165607496232909730
255 2234762919005159040
256 2305843009750581376
257 2378893500495463041
258 2453961025236747684
259 2531093134117903810
260 2610338307771237030
261 2691745971827944851
262 2775366511597216846
263 2861251286915688084
264 2949452647168558740
265 3040023946483697845
266 3133019559100054176
267 3228494894911702326
268 3326506415188857034
269 3427111648477193895
270 3530369206676819610
271 3636338801302239976
272 3745081259924678856
273 3856658542798106409
274 3971133759670339900
275 4088571186780585450
276 4209036284044794126
277 4332595712430210811
278 4459317351520499334
279 4589270317272832380
280 4722524979968339740
281 4859152982357313501
282 4999227258000573816
283 5142822049808403934
284 5290012928778468210
285 5440876812934131855
286 5595491986464606226
287 5753938119068348496
288 5916296285501149584
289 6082648985330349265
290 6253080162896622420
291 6427675227484785426
292 6606521073705076726
293 6789706102086370659
294 6977320239882788670
295 7169454962095177060
296 7366203312708925476
297 7567659926149605381
298 7773921048957912784
299 7985084561685404550
300 8201250001012522650
301 8422518582090405751
302 8648993221107992586
303 8880778558085926584
304 9117980979898776280
305 9360708643527091065
306 9609071499540816876
307 9863181315815601466
308 10123151701483523934
309 10389098131119788235
310 10661137969166925430
311 10939390494598054476
312 11223976925820756396
313 11515020445823121709
314 11812646227563536040
315 12116981459605773870
316 12428155372000975426
317 12746299262418086751
318 13071546522524348034
319 13404032664617420320
320 13743895348510745760
321 14091274408673741601
322 14446311881628433156
323 14809152033604136034
324 15179941388451802950
325 15558828755819655475
326 15945965259591726126
327 16341504366590941236
328 16745601915548380084
329 17158416146340350805
330 17580107729494928640
331 18010839795969607126
332 18450777967201717866
333 18900090385433279559
334 19358947744311942010
335 19827523319769695880
336 20305993001181023976
337 20794535322802174921
338 21293331495493245084
339 21802565438724759690
340 22322423812870449070
341 22853096051787921051
342 23394774395688935526
343 23947653924300992284
344 24511932590321948220
345 25087811253169385085
346 25675493713026453976
347 26275186745185927806
348 26887100134694198034
349 27511446711296956975
350 28148442384688312050
351 28798306180065083376
352 29461260273988041136
353 30137530030551844209
354 30827344037865446580
355 31530934144844743090
356 32248535498319231126
357 32980386580454469891
358 33726729246492123934
359 34487808762809382660
360 35263873845299552580
361 36055176698075624101
362 36861973052498619696
363 37684522206532535334
364 38523087064427692090
365 39377934176734319895
366 40249333780648200426
367 41137559840690201176
368 42042890089721537784
369 42965606070296606745
370 43905993176355235660
371 44864340695256203226
372 45840941850153886206
373 46836093842719895659
374 47850097896211569750
375 48883259298889195500
376 49935887447783836876
377 51008295892817651661
378 52100802381278584584
379 53213728902651329230
380 54347401733806456290
381 55502151484549610751
382 56678313143532685666
383 57876226124528885184
384 59096234313073594560
385 60338686113472979905
386 61603934496182245476
387 62892337045555481346
388 64204256007969039334
389 65540058340320380115
390 66900115758904339470
391 68284804788668766676
392 69694506812851493076
393 71129608123000593909
394 72590499969379911520
395 74077578611761813110
396 75591245370609161226
397 77131906678648480231
398 78699974132836307034
399 80295864546720719400
400 81920000003200040200
401 83572807907680721001
402 85254721041636413436
403 86966177616570241834
404 88707621328382295630
405 90479501412144365115
406 92282272697283949126
407 94116395663179568316
408 95982336495169422684
409 97880567140975437085
410 99811565367544743480
411 101775814818310653726
412 103773805070875181746
413 105806031695115178959
414 107872996311714151890
415 109975206651121835920
416 112113176612943604176
417 114287426325761795601
418 116498482207391051284
419 118746877025569753170
420 121033149959089664310
421 123357846659365874851
422 125721519312449163006
423 128124726701482885284
424 130568034269606515300
425 133052014183307955525
426 135577245396226751376
427 138144313713410342086
428 140753811856025487834
429 143406339526527017655
430 146102503474286047690
431 148842917561679824376
432 151628202830645352216
433 154458987569698970809
434 157335907381424050860
435 160259605250428983930
436 163230731611777645726
437 166249944419894517771
438 169317909217946657334
439 172435299207704710540
440 175602795319885168620
441 178821086284976072301
442 182090868704548374376
443 185412847123055175534
444 188787734100121053570
445 192216250283323711135
446 195699124481470172226
447 199237093738369762656
448 202830903407106114784
449 206481307224810441825
450 210189067387938332100
451 213954954628052318626
452 217779748288112484486
453 221664236399277369459
454 225609215758217448430
455 229615492004943457140
456 233683879701151845876
457 237815202409089646741
458 242010292770941045184
459 246269992588737951510
460 250595152904796873130
461 254986634082684393351
462 259445305888713567546
463 263972047573973552584
464 268567747956894790440
465 273233305506352071945
466 277969628425307811676
467 282777634734997870026
468 287658252359662263534
469 292612419211823109595
470 297641083278112156710
471 302745202705650256476
472 307925745888981138556
473 313183691557561854909
474 318520028863812264600
475 323935757471725935550
476 329431887646044844626
477 335009440342000262511
478 340669447295622214834
479 346412951114619916080
480 352241005369835577840
481 358154674687273998001
482 364155034840710342516
483 370243172844878536434
484 376420187049242685910
485 382687187232353957955
486 389045294696795349726
487 395495642364716784196
488 402039374873962974084
489 408677648674796500965
490 415411632127218561520
491 422242505598889837926
492 429171461563653954426
493 436199704700665987159
494 443328451994128499370
495 450558932833637579160
496 457892389115141361976
497 465330075342513525081
498 472873258729744246284
499 480523219303751124250
500 488281250007812562750
501 496148656805626126251
502 504126758785994379286
503 512216888268140727084
504 520420390907657779980
505 528738625803090769165
506 537172965603158546376
507 545724796614614705166
508 554395518910751366434
509 563186546440548175935
510 572099307138469066530
511 581135243034909342976
512 590295810367295652096
513 599582479691841406209
514 608996735995960232740
515 618540078811340027970
516 628214022327680197926
517 638020095507094674451
518 647959842199183299534
519 658034821256774176020
520 668246606652339587860
521 678596787595088098101
522 689086968648735437856
523 699718769849956804534
524 710493826827523192650
525 721413790922124385575
526 732480329306881241626
527 743695125108549912936
528 755059877529420640584
529 766576301969913774505
530 778246130151875671740
531 790071110242577131626
532 802053006979417031566
533 814193601795333832059
534 826494692944927624710
535 838958095631295401980
536 851585642133582232476
537 864379181935251030621
538 877340581853073614584
539 890471726166845751390
540 903774516749828893170
541 917250873199921313551
542 930902732971561358226
543 944732051508365528784
544 958740802376504123920
545 972930977398817167185
546 987304586789673355476
547 1001863659290574767506
548 1016610242306510076534
549 1031546402043059016675
550 1046674223644250857150
551 1061995811331179643876
552 1077513288541378972836
553 1093228798068959064709
554 1109144502205508915280
555 1125262582881766301190
556 1141585241810058425626
557 1158114700627515993591
558 1174853201040063511434
559 1191803004967188610360
560 1208966394687493198680
561 1226345672985029252601
562 1243943163296422060396
563 1261761209858783739834
564 1279802177858419853790
565 1298068453580331953995
566 1316562444558518887926
567 1335286579727079708876
568 1354243309572121034284
569 1373435106284471702445
570 1392864463913207582760
571 1412533898519989399726
572 1432445948334216435906
573 1452603173908998984159
574 1473008158277952424450
575 1493663507112815805600
576 1514571848881897817376
577 1535735835009353043361
578 1557158140035291390084
579 1578841461776723592930
580 1600788521489345704390
581 1623002064030165475251
582 1645484858020973544366
583 1668239696012662357684
584 1691269394650395742260
585 1714576794839632066005
586 1738164761913003918976
587 1762036185798057257046
588 1786193981185852953834
589 1810641087700433711815
590 1835380470069159288570
591 1860415118293912999176
592 1885748047823182460776
593 1911382299725017550409
594 1937320940860868552220
595 1963567064060307475210
596 1990123788296635527726
597 2016994258863379739931
598 2044181647551681730534
599 2071689152828581619100
600 2099520000016200090300
601 2127677441471821621501
602 2156164756768881890136
603 2184985252878862382334
604 2214142264354095229330
605 2243639153511481303215
606 2273479310617124608626
607 2303666154071886012016
608 2334203130597859355184
609 2365093715425773004785
610 2396341412483319894580
611 2427949754584419122226
612 2459922303619412167446
613 2492262650746196803459
614 2524974416582301778590
615 2558061251397905350020
616 2591526835309800756676
617 2625374878476311723301
618 2659609121293161092784
619 2694233334590295688870
620 2729251319829670516410
621 2764666909303995411351
622 2800483966336447257706
623 2836706385481350893784
624 2873338092725831835000
625 2910383045692443945625
626 2947845233842775196876
627 2985728678682034653786
628 3024037433964623838334
629 3062775585900695621355
630 3101947253363703800790
631 3141556588098946528876
632 3181607774933106755916
633 3222105031984792863309
634 3263052610876082663560
635 3304454796945073950030
636 3346315909459444784226
637 3388640301831026713471
638 3431432361831394116834
639 3474696511808472882240
640 3518437208904171622720
641 3562658945273038644801
642 3607366248301947887076
643 3652563680830817052034
644 3698255841374361159270
645 3744447364344884753235
646 3791142920276116003726
647 3838347216048085942356
648 3886064995113056083284
649 3934301037722497681525
650 3983060161155125887200
651 4032347219945992059126
652 4082167106116637506186
653 4132524749406311929959
654 4183425117504259847130
655 4234873216283078275240
656 4286874090033148970376
657 4339432821698148510441
658 4392554533111639522684
659 4446244385234746359210
660 4500507578394918529230
661 4555349352525785201851
662 4610774987408104098246
663 4666789802911808097084
664 4723399159239152882140
665 4780608457168968966045
666 4838423138302021429176
667 4896848685307480717726
668 4955890622170507850034
669 5015554514440957385295
670 5075845969483201513810
671 5136770636727078632976
672 5198334207919969778256
673 5260542417380006283409
674 5323401042250412049300
675 5386915902754983805650
676 5451092862454712755126
677 5515937828505550994211
678 5581456751917326110334
679 5647655627813807359780
680 5714540495693926835940
681 5782117439694159042501
682 5850392588852062291216
683 5919372117370985348934
684 5989062244885942763610
685 6059469236730662304055
686 6130599404205807953226
687 6202459104848381899896
688 6275054742702308978584
689 6348392768590207012665
690 6422479680386346520620
691 6497322023290803250426
692 6572926390104807012126
693 6649299421507290283659
694 6726447806332640070070
695 6804378281849656501260
696 6883097634041721658476
697 6962612697888182124781
698 7042930357646948759784
699 7124057547138317203950
700 7206001250030012622850
701 7288768500123462206751
702 7372366381641298945986
703 7456802029516100207584
704 7542082629680364643680
705 7628215419357730967265
706 7715207687355442135876
707 7803066774358058488866
708 7891800073222423388934
709 7981415029273884923635
710 8071919140603777227630
711 8163319958368164991476
712 8255625087087854727796
713 8348842184949676370709
714 8442978964109038789440
715 8538043190993762802070
716 8634042686609195280426
717 8730985326844607942151
718 8828879042780884431034
719 8927731820999499291720
720 9027551703892792449960
721 9128346789975542814601
722 9230125234197844622556
723 9332895248259290153034
724 9436665100924462442350
725 9541443118339741635675
726 9647237684351428617126
727 9754057240825189564636
728 9861910287966825081084
729 9970805384644367558205
730 10080751148711510434840
731 10191756257332373016126
732 10303829447307604525266
733 10416979515401831064559
734 10531215318672449167410
735 10646545774799769628080
736 10762979862418515300976
737 10880526621450676566321
738 10999195153439728164084
739 11118994621886211103090
740 11239934252584683357270
741 11362023333962043066051
742 11485271217417227960926
743 11609687317662294745284
744 11735281113064882159620
745 11862062145992061469285
746 11990040023155578116976
747 12119224415958488287206
748 12249625060843194135034
749 12381251759640881436375
750 12514114379922363422250
751 12648222855350334564376
752 12783587186033038084536
753 12920217438879350965209
754 13058123747955290243980
755 13197316314841944379290
756 13337805408994833480126
757 13479601368104702197291
758 13622714598459749078934
759 13767155575309296198060
760 13912934843228902864780
761 14060063016486927241101
762 14208550779412539681096
763 14358408886765191624334
764 14509648164105543875490
765 14662279508167858108095
766 14816313887233855435426
767 14971762341508045896576
768 15128635983494532710784
769 15286945998375295158145
770 15446703644389953949860
771 15607920253217022956226
772 15770607230356651165606
773 15934776055514858752659
774 16100438282989271139150
775 16267605542056354935700
776 16436289537360159657876
777 16606502049302569115061
778 16778254934435066375584
779 16951560125852016216630
780 17126429633585468972490
781 17302875545001489699751
782 17480910025198016583066
783 17660545317404252510184
784 17841793743381593749960
785 18024667703826099672105
786 18209179678772507452476
787 18395342227999795712746
788 18583167991438301048334
789 18772669689578391403515
790 18963860123880700257670
791 19156752177187925591676
792 19351358814138197608476
793 19547693081580019186909
794 19745768108988783052920
795 19945597108884869657310
796 20147193377253329754226
797 20350570293965155679631
798 20555741323200145334034
799 20762720013871362878800
800 20971520000051200160400
801 21182155001399042882001
802 21394638823590545546836
803 21608985358748519202834
804 21825208585875436023030
805 22043322571287554761315
806 22263341469050671128126
807 22485279521417497135716
808 22709151059266673467684
809 22934970502543418932485
810 23162752360701821065680
811 23392511233148771950726
812 23624261809689553333146
813 23858018870975075107959
814 24093797288950771265290
815 24331612027307157384120
816 24571478141932053769176
817 24813410781364478331001
818 25057425187250213314284
819 25303536694799049984570
820 25551760733243715388510
821 25802112826300485307851
822 26054608592631487532406
823 26309263746308699582284
824 26566094097279645014700
825 26825115551834792455725
826 27086344113076661502376
827 27349795881390639645486
828 27615487054917514368834
829 27883433930027724585055
830 28153652901797335573890
831 28426160464485741593376
832 28700973212015100339616
833 28978107838451503435809
834 29257581138487887136260
835 29539410007928687436130
836 29823611444176243782726
837 30110202546718955589171
838 30399200517621195756334
839 30690622662014985413940
840 30984486388593434096820
841 31280809210105949577301
842 31579608743855221579776
843 31880902712195983608534
844 32184708943035557124970
845 32491045370336182315335
846 32799930034619139695226
847 33111381083470666802056
848 33425416772049674231784
849 33742055463597265281225
850 34061315629948063462300
851 34383215852043352159626
852 34707774820446030707886
853 35035011335857391170459
854 35364944309635720105830
855 35697592764316729613340
856 36032975834135821954876
857 36371112765552192054141
858 36712022917774772180184
859 37055725763290023126910
860 37402240888391576205330
861 37751587993711730370351
862 38103786894754808808946
863 38458857522432379321584
864 38816819923600342833840
865 39177694261597894380145
866 39541500816788360906676
867 39908259987101920245426
868 40277992288580205616534
869 40650718355922800020995
870 41026458943035624890910
871 41405234923581227369476
872 41787067291530970597956
873 42171977161719131391909
874 42559985770398909694000
875 42951114475800354195750
876 43345384758690208525626
877 43742818222933682405911
878 44143436596058152185834
879 44547261729818795163480
880 44954315600766162114040
881 45364620310815692447001
882 45778198087819176419916
883 46195071286138168841434
884 46615262387219358701310
885 47038794000171899170155
886 47465688862346702416726
887 47895969839917703695596
888 48329659928465099163084
889 48766782253560561884365
890 49207360071354440499720
891 49651416769164945022926
892 50098975866069324249826
893 50550061013497039260159
894 51004695995824937500770
895 51462904730974431943360
896 51924711271010689814976
897 52390139802743835404481
898 52859214648332171453284
899 53331960265887423643650
900 53808401250082012702950
901 54288562332758358647251
902 54772468383540221692686
903 55260144410446084368084
904 55751615560504579367380
905 56246907120371967685365
906 56746044516951671585376
907 57249053318015866952566
908 57755959232829139591434
909 58266788112774210031335
910 58781565951979731408730
911 59300318887950164999976
912 59823073202197737983496
913 60349855320876488015209
914 60880691815418399206140
915 61415609403171634096170
916 61954634948040866222926
917 62497795461129717889851
918 63045118101385307742534
919 63596630176244912767420
920 64152359142284749332060
921 64712332605870877891101
922 65276578323812235987256
923 65845124204015804181534
924 66417998306143909552050
925 66995228842273671405775
926 67576844177558593852626
927 68162872830892309896336
928 68753343475574481701584
929 69348284939978861701905
930 69947726208223519217940
931 70551696420843237260626
932 71160224875464084198966
933 71773341027480164977059
934 72391074490732556570110
935 73013455038190432374180
936 73640512602634380229476
937 74272277277341918782021
938 74908779316775216893584
939 75550049137271020814790
940 76196117317732793841370
941 76847014600325073178551
942 77502771891170048743626
943 78163420261046368641784
944 78828990946090176055320
945 79499515348498382291385
946 80175025037234180738476
947 80855551748734806486906
948 81541127387621546373534
949 82231784027412004216075
950 82927553911234626007350
951 83628469452545489844876
952 84334563235847365376236
953 85045868017411047545709
954 85762416725998969432680
955 86484242463591098977390
956 87211378506113124394626
957 87943858304166933080991
958 88681715483763388826434
959 89424983847057412145760
960 90173697373085368550880
961 90927890218504769589601
962 91687596718336291481796
963 92452851386708116188834
964 93223688917602599757190
965 94000144185605272782195
966 94782252246656177842926
967 95570048338803548764276
968 96363567882959836567284
969 97162846483660086973845
970 97967919929822674336960
971 98778824195512396872726
972 99595595440705938075306
973 100418270012059699201159
974 101246884443680007713850
975 102081475457895706585800
976 102922079966033129358376
977 103768735069193465866761
978 104621478059032523541084
979 105480346418542889200330
980 106345377822838496260590
981 107216610139941602284251
982 108094081431572181801766
983 108977829953939739342684
984 109867894158537547617660
985 110764312692939315798205
986 111667124401598292845976
987 112576368326648810848446
988 113492083708710273322834
989 114414309987693593455215
990 115343086803610087246770
991 116278453997382826544176
992 117220451611660456936176
993 118169119891633485503409
994 119124499285853043413620
995 120086630447052128359410
996 121055554232969331840726
997 122031311707175056299331
998 123013944139900227117534
999 124003493008867504498500
1000 125000000000125000250500