0 1
1 3
2 9
3 27
4 1
5 81
6 6
7 243
8 27
9 729
10 108
11 1
12 2187
13 405
14 9
15 6561
16 1458
17 54
18 19683
19 5103
20 270
21 1
22 59049
23 17496
24 1215
25 12
26 177147
27 59049
28 5103
29 90
30 531441
31 196830
32 20412
33 540
34 1
35 1594323
36 649539
37 78732
38 2835
39 15
40 4782969
41 2125764
42 295245
43 13608
44 135
45 14348907
46 6908733
47 1082565
48 61236
49 945
50 1
51 43046721
52 22320522
53 3897234
54 262440
55 5670
56 18
57 129140163
58 71744535
59 13817466
60 1082565
61 30618
62 189
63 387420489
64 229582512
65 48361131
66 4330260
67 153090
68 1512
69 1
70 1162261467
71 731794257
72 167403915
73 16888014
74 721710
75 10206
76 21
77 3486784401
78 2324522934
79 573956280
80 64481508
81 3247695
82 61236
83 252
84 10460353203
85 7360989291
86 1951451352
87 241805655
88 14073345
89 336798
90 2268
91 1
92 31381059609
93 23245229340
94 6586148313
95 892820880
96 59108049
97 1732104
98 17010
99 24
100 94143178827
101 73222472421
102 22082967873
103 3252418920
104 241805655
105 8444007
106 112266
107 324
108 282429536481
109 230127770466
110 73609892910
111 11708708112
112 967222620
113 39405366
114 673596
115 3240
116 1
117 847288609443
118 721764371007
119 244074908070
120 41712272649
121 3794488740
122 177324147
123 3752892
124 26730
125 27
126 2541865828329
127 2259436291848
128 805447196631
129 147219785820
130 14635885140
131 773778096
132 19702683
133 192456
134 405
135 7625597484987
136 7060738412025
137 2646469360359
138 515269250370
139 55616363532
140 3288556908
141 98513415
142 1250964
143 4455
144 1
145 22876792454961
146 22029503845518
147 8661172452084
148 1789882659180
149 208561363245
150 13660159464
151 472864392
152 7505784
153 40095
154 30
155 68630377364883
156 68630377364883
157 28242953648100
158 6175095174171
159 772903875555
160 55616363532
161 2192371272
162 42220035
163 312741
164 495
165 205891132094649
166 213516729579636
167 91789599356325
168 21171754882872
169 2833980877035
170 222465454128
171 9865670724
172 225173520
173 2189187
174 5940
175 1
176 617673396283947
177 663426981193869
178 297398301914493
179 72176437100700
180 10291825290285
181 875957725629
182 43257171636
183 1148384952
184 14073345
185 57915
186 33
187 1853020188851841
188 2058911320946490
189 960825283108362
190 244772264950200
191 37050571045026
192 3400777052442
193 185387878440
194 5637526128
195 84440070
196 486486
197 594
198 5559060566555523
199 6382625094934119
200 3095992578904722
201 826106394206925
202 132323468017950
203 13036312034361
204 778629089448
205 26778249108
206 478493730
207 3648645
208 7722
209 1
210 16677181699666569
211 19765548681086304
212 9951404717908035
213 2775717484535268
214 469146841154550
215 49400761393368
216 3211844993973
217 123591918960
218 2583866142
219 25019280
220 81081
221 36
222 50031545098999707
223 61149666232110753
224 31913125474670595
225 9287977736714166
226 1652212788413850
227 185252855225130
228 13036312034361
229 556163635320
230 13389124554
231 159497910
232 729729
233 702
234 150094635296999121
235 189008059262887782
236 102122001518945904
237 30959925789047220
238 5782744759448475
239 688082033693340
240 52145248137444
241 2447119995408
242 66945622770
243 956987460
244 5837832
245 9828
246 1
247 450283905890997363
248 583701359488329915
249 326131553237924016
250 102831182085049695
251 20123951762880693
252 2533392942234570
253 205836505805700
254 10553204980197
255 324428787270
256 5454828522
257 42532776
258 110565
259 39
260 1350851717672992089
261 1801135623563989452
262 1039544325945882801
263 340406671729819680
264 69659833025356245
265 9252391615117560
266 802762372642230
267 44695926974952
268 1529449997130
269 29753610120
270 287096238
271 1061424
272 819
273 4052555153018976267
274 5553501505988967477
275 3307641037100536185
276 1123342016708404944
277 239939424865115955
278 33539919604801155
279 3096369151620030
280 186233029062300
281 7035469986798
282 156206453130
283 1818276174
284 9022104
285 12285
286 1
287 12157665459056928801
288 17110788423857899794
289 10506624470789938470
290 3696157603363138848
291 822649456680397560
292 120743710577284158
293 11822500397094660
294 764535592992600
295 31659614940591
296 793048146660
297 10909657044
298 69599088
299 147420
300 42
301 36472996377170786403
302 52683216989246691471
303 33321009035933804862
304 12128017136035299345
305 2808355041771012360
306 431890964757208719
307 44719892806401540
308 3096369151620030
309 139674771796725
310 3908594437110
311 62482581252
312 495893502
313 1503684
314 945
315 109418989131512359209
316 162102206120759050680
317 105516528613790382063
318 39691692445206434220
319 9548407142021442024
320 1535612319136742112
321 167699598024005775
322 12385476606480120
323 605257344452475
324 18761253298128
325 343654196886
326 3305956680
327 13533156
328 15120
329 1
330 328256967394537077627
331 498464283821334080841
332 333660374265229045983
333 129581701806409241130
334 32341379029427464920
335 5429486414090623896
336 623842504649301483
337 48978930216535020
338 2580307626350025
339 87943374834975
340 1824010737318
341 20827527084
342 110198556
343 192780
344 45
345 984770902183611232881
346 1531865847841173028926
347 1053664339784933829420
348 422066114455161528252
349 109152154224317694105
350 19096814284042884048
351 2303418478705113168
352 191656683456006600
353 10837292030670105
354 403504896301650
355 9380626649064
356 124965162504
357 826489170
358 2082024
359 1080
360 2954312706550833698643
361 4705016532655031445987
362 3323095225475560538940
363 1371714871979274966819
364 367148155118159516535
365 66838849994150094168
366 8445867755252081616
367 742669648392025575
368 44897352698490435
369 1815772033357425
370 46903133245320
371 718549684398
372 5785424190
373 19779228
374 18360
375 1
376 8862938119652501095929
377 14443306565359631415588
378 10467749960248015697661
379 4448804990203053946440
380 1231026167160887790735
381 232857929011877747424
382 30767089679846868744
383 2851851449825378208
384 183670988312006325
385 8027623726422300
386 228652774570935
387 3979659790512
388 38183799654
389 169536240
390 247860
391 48
392 26588814358957503287787
393 44314690598262505479645
394 32935115728585220121909
395 14400079310394095668740
396 4115144615937824900457
397 807725941259950936377
398 111398083323583490280
399 10858972828181247792
400 742669648392025575
401 34920163209937005
402 1089463220014455
403 21319606020600
404 239516561466
405 1335097890
406 2825604
407 1224
408 79766443076872509863361
409 135898384501338350137578
410 103510363718410691811714
411 46523333156657847545160
412 13717148719792749668190
413 2790325978898012325666
414 401033099964900565008
415 41022786239795824992
416 2970678593568102300
417 149657842328301450
418 5084161693400790
419 110861951307120
420 1437099368796
421 9790717860
422 28256040
423 22032
424 1
425 239299329230617529590083
426 416558091623667551508663
427 324974397720591706850730
428 150037749430221558333141
429 45600251149581302951010
430 9602004103854924767733
431 1435957228906579442448
432 153835448399234343720
433 11763887230529685108
434 632644515296910675
435 23280108806624670
436 561238628492295
437 8290957896900
438 67555953234
439 254304360
440 313956
441 51
442 717897987691852588770249
443 1276263089229960157813776
444 1019237883760037626031835
445 483048364019249895121332
446 151200832759138004521770
447 32921156927502599203656
448 5115597627979689263721
449 572904428521286521440
450 46150634519770303116
451 2640603194282757600
452 104760489629811015
453 2773179105491340
454 46192479711300
455 442184421168
456 2098010970
457 3767472
458 1377
459 2153693963075557766310747
460 3908555710766752983304689
461 3193612035781451228233083
462 1552655455776160377175710
463 500125831434071861110470
464 112480619502300547279158
465 18137118862837080116829
466 2119746385528760129328
467 179474689799106734340
468 10892488176416375100
469 463939311217734495
470 13403699009874810
471 249439390441020
472 2763652632300
473 16084750770
474 39558456
475 26163
476 1
477 6461081889226673298932241
478 11964966461530876479504150
479 9997394198968021236207912
480 4982940765049072838377860
481 1650415243732437141664551
482 383042109656482944788484
483 64013360692366165118220
484 7795196385492859830432
485 692259517796554546740
486 44441351759778810408
487 2024462448950114160
488 63491205836249100
489 1309556799815355
490 16581915793800
491 115810205544
492 372979728
493 392445
494 54
495 19383245667680019896796723
496 36612797372284482027282699
497 31268445686134023866437512
498 15968060178907256141165415
499 5434294095216561320114985
500 1300327161728586838887222
501 224961239004601094558316
502 28501186784458268755017
503 2649682981910950161660
504 179474689799106734340
505 8713990541133100080
506 295234107138558315
507 6701849504937405
508 95938227092700
509 789615037800
510 3216950154
511 4944807
512 1539
513 58149737003040059690390169
514 111992086079929003848158844
515 97713892769168824582617225
516 51097792572503219651729328
517 17855537741425844337520665
518 4401107316619832377772136
519 787364336516103830954106
520 103640679216211886381880
521 10068795331261610614308
522 717898759196426937360
523 37034459799815675340
524 1349641632633409440
525 33509247524687025
526 537254071719120
527 5132497745700
528 25735601232
529 54392877
530 30780
531 1
532 174449211009120179071170507
533 342437340129013684843408773
534 305106644769037350227355825
535 163290771916477680191395896
536 58549553989326605850939855
537 14853737193591934274980959
538 2745135119204794437650802
539 374935398341001824263860
540 38001582379277691673356
541 2845955795385835358820
542 155544731159225836428
543 6073387346850342480
544 164018948410310175
545 2921319014972715
546 31979409030900
547 193017009240
548 536158359
549 484785
550 57
551 523347633027360537213511521
552 1046695266054721074427023042
553 951932731679396532709350174
554 521140761435567064440625200
555 191616722146887073693984980
556 49995505675992364145057862
557 9535732519342970151839628
558 1349767434027606567349896
559 142505933922291343775085
560 11187550368068456238120
561 646108883276784243624
562 26934152581684127520
563 787290952369488840
564 15465806549855550
565 191876454185400
566 1368666065520
567 4825425231
568 6399162
569 1710
570 1570042899082081611640534563
571 3198235535167203282971459295
572 2967790281118118601976209366
573 1661136177075870017904492825
574 625947959013164440733684268
575 167842054769402936772694251
576 33008304874648742833291020
577 4836666638598923533003794
578 531158480983085917707135
579 43631446435466979328668
580 2656225409026779668232
581 117836917544868057900
582 3711514489741875960
583 79906667174253675
584 1112883434275320
585 9238495942260
586 40211876925
587 73590363
588 35910
589 1
590 4710128697246244834921603689
591 9769155816510730027985548392
592 9245808183483369490772036871
593 5288515175996647403940834300
594 2041134648955971002392448700
595 562075718297535416169022608
596 113878651817538162774854019
597 17255135035001565036662184
598 1968410841290259577385265
599 168895921685678629659360
600 10814632022466174363516
601 509055483793830010128
602 17207930816075970360
603 403738949933071200
604 6259969317798675
605 59694896857680
606 313652640015
607 756929448
608 592515
609 60
610 14130386091738734504764811067
611 29830815082559550621170156697
612 28784119816504829546743133655
613 16817478259669338744531853074
614 6644544708303480071617971300
615 1877843877039493322201052804
616 391631461128606852469619919
617 61301137624347665261826180
618 7254999957898385299505691
619 649193698979327232753165
620 43631446435466979328668
621 2173275334658274274008
622 78557945029912038600
623 1998507802168702440
624 34245714503251575
625 370961144758440
626 2309623985565
627 7096213575
628 8176707
629 1890
630 42391158275216203514294433201
631 91062488146760733475151004654
632 89550594984681691923200860260
633 53420225060126134835571768588
634 21594770301986310232758406725
635 6259479590131644407336842680
636 1342736438155223494181554008
637 216911717747691738618769560
638 26601666512294079431520867
639 2478739577921067615966630
640 174525785741867917314672
641 9176051413001602490256
642 353510752634604173700
643 9707037896247983280
644 182643810684008400
645 2225766868550640
646 16167367898955
647 61500517650
648 98120484
649 41580
650 1
651 127173474825648610542883299603
652 277897593137528445260374617651
653 278420940770555805797588129172
654 169506483363861773997487342635
655 70072826081955578102216054475
656 20819573419350904224402976740
657 4590285032763205898713684632
658 764613805060613378631162699
659 97060134571883803331224785
660 9404629575053462425285155
661 692473278911282381603376
662 38342786261470981834284
663 1569587741697642531228
664 46329044504819920200
665 951670381985096400
666 12937269923450595
667 108197000554545
668 498154192965
669 1051290900
670 717255
671 63
672 381520424476945831628649898809
673 847823165504324070285888664020
674 865093637394226968013934544213
675 537303569908090151539205161560
676 227035956505536073051180016499
677 69103264966356192744826901520
678 15648698975329111018342106700
679 2685472876310446988363108016
680 352481541339999075255500535
681 35468888683058772575361156
682 2726613535713174377563293
683 158659805219879924831520
684 6882038559751201867692
685 217545078544371799200
686 4853518948123991640
687 73057524273603360
688 695552146422075
689 3804086564460
690 10250086275
691 10328472
692 2079
693 1144561273430837494885949696427
694 2585860654788188414371960425261
695 2686343400329441637516954637293
696 1701461304708952146540816344940
697 734528094576734353989111818085
698 228904565201054888467239111285
699 53205576516118977462363162780
700 9399155067086564459270878056
701 1274356341767688964385271165
702 133008332561470397157604335
703 10658580185060590748656509
704 650505201401507691809232
705 29822167092255208093332
706 1006145988267719571300
707 24267594740619958200
708 401816383504818480
709 4312423307816865
710 27579627592335
711 92250776475
712 129105900
713 47817
714 1
715 3433683820292512484657849089281
716 7884755439190213853658764575386
717 8336927794125853357811238529530
718 5382804854897412245420037163992
719 2373090767094064835964822796890
720 756786521685120243503933388330
721 180436302967707836611492465080
722 32787750234022899276526318800
723 4587682830363680271786976194
724 496085132256294994804037790
725 41380370130235234671254682
726 2643988883115805457031072
727 127809287538236606114280
728 4588025706500801245128
729 119131828726679794800
730 2157119532499551840
731 25874539846901190
732 190935883331550
733 774906522390
734 1438608600
735 860706
736 66
737 10301051460877537453973547267843
738 24035786742047587392604943624967
739 25858606547881884143719604252610
740 17013508202086463704274046036189
741 7656575871190284659433673552230
742 2497395521560896803562980181489
743 610412173869479702579304296760
744 114011949677397808847921063100
745 16448521367401487803724036598
746 1840736938108884059667613905
747 159609999073764476589125202
748 10658580185060590748656509
749 542087667834589743174360
750 20646115679253605603076
751 574940564724411183600
752 11324877545622647160
753 150681143814306930
754 1268359796416725
755 6128806131630
756 14565912075
757 12910590
758 2277
759 30903154382632612361920641803529
760 73251921499573599672700780571328
761 80161680298433840845530773183091
762 53726868006588832750339092745860
763 24671188918279806124841837001630
764 8226714659259424764678052362552
765 2060141086809493996205152001565
766 395241425548312404006126352080
767 58744719169291027870442987850
768 6796567156094341143388112880
769 611838329782763826924979941
770 42634320740242362994626036
771 2276768204905276921332312
772 91760514130016024902560
773 2730967682440953122100
774 58242227377487899680
775 853859814947739270
776 8117502697067040
777 45966045987225
778 135948512700
779 167837670
780 54648
781 1
782 92709463147897837085761925410587
783 223189448319013311502760190803265
784 248369796334491736390251084124659
785 169517531813892351608828516767110
786 79396371609736830619945548168882
787 27053234744872339129998979884546
788 6937209782113602232119389393025
789 1366160579612645048629871521320
790 209021907741895982887855282350
791 24977384298646703701951314834
792 2331600121604586475578977613
793 169283332350962323655132790
794 9474293497831636221028008
795 403090829928284680821960
796 12780928753823660611428
797 293858510859143493840
798 4718698977342769650
799 50227047938102310
800 328834021293225
801 1182752060490
802 1942121610
803 1024650
804 69
805 278128389443693511257285776231761
806 679869396417917471962254119677638
807 769145175745522796563358195998944
808 534411201989558938970205154553940
809 255202623031296955564110690542835
810 88816280105807302049430613205868
811 23309024867901703499921148360564
812 4708893912707414848468918860720
813 741077672903085757511486910150
814 91380674263341598909577981100
815 8835537302922643486404546744
816 667459996126651447554523572
817 39081460678555499411740533
818 1751360157619443785640240
819 58988901940724587437360
820 1456516097301841665120
821 25480974477650956110
822 301362287628613860
823 2254861860296400
824 9677062313100
825 20392276905
826 15984540
827 2484
828 834385168331080533771857328695283
829 2070511343636385028248683000836443
830 2380687448736141989362775368568160
831 1683395286267110657756146236844911
832 819334737100479699442671164374365
833 291120029235701712273133676619234
834 78153789262964535264441497444244
835 16186822824931738541611908583725
836 2618474444257569676540587082530
837 332886741959315824599176931150
838 33303179064862271602601753112
839 2614218318162718169588550657
840 159878702775908861229847635
841 7530848677763608278253032
842 268727219952189787214640
843 7100515974346478117460
844 134685150810440768010
845 1757946677833580850
846 14882088277956240
847 74997232926525
848 197125343415
849 215791290
850 62100
851 1
852 2503155504993241601315571986085849
853 6304243494057052921831810927919916
854 7365251794527439279591086296507745
855 5298555655135823709658689794659392
856 2627521743115331449936842009890205
857 952756459316841967439346578026584
858 261514602533765944923323472217278
859 55497678256908817856955115144200
860 9221583912385354078251632768910
861 1207682133619843456685386075800
862 124886921493233518509756574170
863 10174255076092740984344629584
864 648919440678688907344675695
865 32066839531122461055787104
866 1209272489784854042465880
867 34082476676863094963808
868 697913963290465797870
869 9992539010843512200
870 94873312771971030
871 553825720072800
872 1774128090735
873 2589495480
874 1210950
875 72
876 7509466514979724803946715958257547
877 19190858871614852276752718559991509
878 22775624780000235310735513009200873
879 16664812141152993925539427579977120
880 8416976431335553288780731184224555
881 3113472000981822857882150424622587
882 873360087707105136819401029857702
883 189802059638628157070786493793164
884 32373645649863477083223817167450
885 4364124073762616127567645137550
886 466041438743042154438847703610
887 39358302531200866439438435496
888 2614218318162718169588550657
889 135281979271922882579101845
890 5379177626974005913037880
891 161236331971313872328784
892 3550257987173239058730
893 55458591510181492710
894 585982225944526950
895 3916339020514800
896 14999446585305
897 28160763345
898 19617390
899 2700
900 22528399544939174411840147874772641
901 58406961783175637364030013008669810
902 70397385683637090960455222028439062
903 52375123872195123765981058108499520
904 26934324580273770524098339789518576
905 10159750740045948273089122438242126
906 2911200292357017122731336766192340
907 647559968178849006476800978823736
908 113307759774522169791283360086075
909 15710846665545418059243522495180
910 1731011058188442287915720041980
911 151378086658464870920917059600
912 10456873272650872678354202628
913 565724640591677508967153170
914 23668381558685626017366672
915 752436215866131404200992
916 17751289935866195293650
917 301060925340985246140
918 3515893355667161700
919 26631105339500640
920 119995572682440
921 281607633450
922 274643460
923 70200
924 1
925 67585198634817523235520443624317923
926 177724040854520153693405611012095279
927 217496400544968325803197477013237102
928 164490623411112810577534260622006305
929 86101529395957135281953709163215120
930 33106773963253176269204209324616583
931 9686357336387893335633356876603604
932 2204194507070312964353726408688486
933 395420957580475327230805195402425
934 56354123909021608255982200254450
935 6400715308185170320432546201740
936 579021181468628131272507752970
937 41544874894045359019407237468
938 2346093362453721434246135205
939 103071984207179339107887120
940 3466581137383248255068856
941 87336346484461680844758
942 1601096739313421536290
943 20540219077844997300
944 174766628790472950
945 913812438120120
946 2618950991085
947 3413425860
948 1421550
949 75
950 202755595904452569706561330872953769
951 540681589078540185884163548994543384
952 671680060506519829686345149599702815
953 516247495013338667043338294875219788
954 274969400329024399771400555069622480
955 107737298321095082096393359158074304
956 32172544010145502864782221054433399
957 7485943608918044029880580255923160
958 1376064932380054138763202080000439
959 201436017376928301851170417930800
960 23566269998318127088865283742770
961 2203104983148926548256370962520
962 163992927213336943497660147900
963 9652498405523882472326956272
964 444497931893460899902763205
965 15778921039123750678244448
966 423245371424698914863058
967 8353548205113503667600
968 117079248743716484610
969 1110282112315945800
970 6657776334875160
971 22856299558560
972 38401040925
973 23882040
974 2925
975 608266787713357709119683992618861307
976 1644573166780559732064330794858402793
977 2073447143302735126423065461807778255
978 1619139870723653092090470106654098426
979 877283324859268323080182723317366960
980 350146219543559016813278417263741488
981 106677382770482456867435785601542323
982 25369031119111149212373077533961820
983 4775754765319011422766407218825053
984 717615811905307075344794613878475
985 86409656660499799325839373723490
986 8340326007635221932684832929540
987 643356868298475701413897503300
988 39414368489222520095335071444
989 1899218436272060208675442785
990 71005144676056878052100016
991 2022172330140228148790166
992 42811934551206706296450
993 652298671572134699970
994 6846739692614999100
995 46604434344126120
996 188564471358120
997 396810756225
998 346289580
999 78975
1000 1