0 1
1 1
2 1
3 1
4 3
5 1
6 6
7 1
8 9
9 1
10 12
11 9
12 1
13 15
14 27
15 1
16 18
17 54
18 1
19 21
20 90
21 27
22 1
23 24
24 135
25 108
26 1
27 27
28 189
29 270
30 1
31 30
32 252
33 540
34 81
35 1
36 33
37 324
38 945
39 405
40 1
41 36
42 405
43 1512
44 1215
45 1
46 39
47 495
48 2268
49 2835
50 243
51 1
52 42
53 594
54 3240
55 5670
56 1458
57 1
58 45
59 702
60 4455
61 10206
62 5103
63 1
64 48
65 819
66 5940
67 17010
68 13608
69 729
70 1
71 51
72 945
73 7722
74 26730
75 30618
76 5103
77 1
78 54
79 1080
80 9828
81 40095
82 61236
83 20412
84 1
85 57
86 1224
87 12285
88 57915
89 112266
90 61236
91 2187
92 1
93 60
94 1377
95 15120
96 81081
97 192456
98 153090
99 17496
100 1
101 63
102 1539
103 18360
104 110565
105 312741
106 336798
107 78732
108 1
109 66
110 1710
111 22032
112 147420
113 486486
114 673596
115 262440
116 6561
117 1
118 69
119 1890
120 26163
121 192780
122 729729
123 1250964
124 721710
125 59049
126 1
127 72
128 2079
129 30780
130 247860
131 1061424
132 2189187
133 1732104
134 295245
135 1
136 75
137 2277
138 35910
139 313956
140 1503684
141 3648645
142 3752892
143 1082565
144 19683
145 1
146 78
147 2484
148 41580
149 392445
150 2082024
151 5837832
152 7505784
153 3247695
154 196830
155 1
156 81
157 2700
158 47817
159 484785
160 2825604
161 9022104
162 14073345
163 8444007
164 1082565
165 1
166 84
167 2925
168 54648
169 592515
170 3767472
171 13533156
172 25019280
173 19702683
174 4330260
175 59049
176 1
177 87
178 3159
179 62100
180 717255
181 4944807
182 19779228
183 42532776
184 42220035
185 14073345
186 649539
187 1
188 90
189 3402
190 70200
191 860706
192 6399162
193 28256040
194 69599088
195 84440070
196 39405366
197 3897234
198 1
199 93
200 3654
201 78975
202 1024650
203 8176707
204 39558456
205 110198556
206 159497910
207 98513415
208 16888014
209 177147
210 1
211 96
212 3915
213 88452
214 1210950
215 10328472
216 54392877
217 169536240
218 287096238
219 225173520
220 59108049
221 2125764
222 1
223 99
224 4185
225 98658
226 1421550
227 12910590
228 73590363
229 254304360
230 495893502
231 478493730
232 177324147
233 13817466
234 1
235 102
236 4464
237 109620
238 1658475
239 15984540
240 98120484
241 372979728
242 826489170
243 956987460
244 472864392
245 64481508
246 531441
247 1
248 105
249 4752
250 121365
251 1923831
252 19617390
253 129105900
254 536158359
255 1335097890
256 1818276174
257 1148384952
258 241805655
259 6908733
260 1
261 108
262 5049
263 133920
264 2219805
265 23882040
266 167837670
267 756929448
268 2098010970
269 3305956680
270 2583866142
271 773778096
272 48361131
273 1
274 111
275 5355
276 147312
277 2548665
278 28857465
279 215791290
280 1051290900
281 3216950154
282 5785424190
283 5454828522
284 2192371272
285 241805655
286 1594323
287 1
288 114
289 5670
290 161568
291 2912760
292 34628958
293 274643460
294 1438608600
295 4825425231
296 9790717860
297 10909657044
298 5637526128
299 967222620
300 22320522
301 1
302 117
303 5994
304 176715
305 3314520
306 41288373
307 346289580
308 1942121610
309 7096213575
310 16084750770
311 20827527084
312 13389124554
313 3288556908
314 167403915
315 1
316 120
317 6327
318 192780
319 3756456
320 48934368
321 432861975
322 2589495480
323 10250086275
324 25735601232
325 38183799654
326 29753610120
327 9865670724
328 892820880
329 4782969
330 1
331 123
332 6669
333 209790
334 4241160
335 57672648
336 536748849
337 3413425860
338 14565912075
339 40211876925
340 67555953234
341 62482581252
342 26778249108
343 3794488740
344 71744535
345 1
346 126
347 7020
348 227772
349 4771305
350 67616208
351 660613968
352 4452294600
353 20392276905
354 61500517650
355 115810205544
356 124965162504
357 66945622770
358 13660159464
359 573956280
360 1
361 129
362 7380
363 246753
364 5349645
365 78885576
366 807417072
367 5750880525
368 28160763345
369 92250776475
370 193017009240
371 239516561466
372 156206453130
373 43257171636
374 3252418920
375 14348907
376 1
377 132
378 7749
379 266760
380 5979015
381 91609056
382 980435016
383 7361127072
384 38401040925
385 135948512700
386 313652640015
387 442184421168
388 343654196886
389 123591918960
390 14635885140
391 229582512
392 1
393 135
394 8127
395 287820
396 6662331
397 105922971
398 1183283640
399 9342968976
400 51757924725
401 197125343415
402 498154192965
403 789615037800
404 718549684398
405 324428787270
406 55616363532
407 1951451352
408 1
409 138
410 8514
411 309960
412 7402590
413 121971906
414 1419940368
415 11765220192
416 69010566300
417 281607633450
418 774906522390
419 1368666065520
420 1437099368796
421 793048146660
422 185387878440
423 11708708112
424 43046721
425 1
426 141
427 8910
428 333207
429 8202870
430 139908951
431 1694767536
432 14706525240
433 91093947516
434 396810756225
435 1182752060490
436 2309623985565
437 2763652632300
438 1824010737318
439 556163635320
440 55616363532
441 731794257
442 1
443 144
444 9315
445 357588
446 9066330
447 159895944
448 2012536449
449 18256376160
450 119122854444
451 552084530400
452 1774128090735
453 3804086564460
454 5132497745700
455 3979659790512
456 1529449997130
457 222465454128
458 6586148313
459 1
460 147
461 9729
462 383130
463 9996210
464 182103714
465 2378452167
466 22516197264
467 154418515020
468 759116229300
469 2618950991085
470 6128806131630
471 9238495942260
472 8290957896900
473 3908594437110
474 778629089448
475 41712272649
476 129140163
477 1
478 150
479 10152
480 409860
481 10995831
482 206712324
483 2798179020
484 27600499872
485 198538090740
486 1032398071848
487 3809383259760
488 9677062313100
489 16167367898955
490 16581915793800
491 9380626649064
492 2447119995408
493 208561363245
494 2324522934
495 1
496 153
497 10584
498 437805
499 12068595
500 233911314
501 3277866852
502 33638109219
503 253307219220
504 1389766635180
505 5465636850960
506 14999446585305
507 27579627592335
508 31979409030900
509 21319606020600
510 7035469986798
511 875957725629
512 22082967873
513 1
514 156
515 11025
516 466992
517 13217985
518 263899944
519 3824177994
520 40773465720
521 320855811012
522 1853022180240
523 7742985538860
524 22856299558560
525 45966045987225
526 59694896857680
527 46192479711300
528 18761253298128
529 3211844993973
530 147219785820
531 387420489
532 1
533 159
534 11475
535 497448
536 14447565
537 296887437
538 4444314966
539 49168002780
540 403657310628
541 2448636452460
542 10840179754404
543 34284449337840
544 74997232926525
545 108197000554545
546 95938227092700
547 46903133245320
548 10553204980197
549 772903875555
550 7360989291
551 1
552 162
553 11934
554 529200
555 15760980
556 333093222
557 5146048908
558 59001603336
559 504571638285
560 3208558110120
561 15009479659944
562 50681359890720
563 119995572682440
564 190935883331550
565 191876454185400
566 110861951307120
567 31659614940591
568 3400777052442
569 73609892910
570 1
571 165
572 12402
573 562275
574 17161956
575 372747177
576 5937748740
577 70474137318
578 626892035445
579 4171125543156
580 20568546200664
581 73910316507300
582 188564471358120
583 328834021293225
584 370961144758440
585 249439390441020
586 87943374834975
587 13036312034361
588 515269250370
589 1162261467
590 1
591 168
592 12879
593 596700
594 18654300
595 416089872
596 6828411051
597 83807082216
598 774396043785
599 5382097475040
600 27914455558044
601 106430855770512
602 291417819371640
603 553825720072800
604 695552146422075
605 537254071719120
606 228652774570935
607 44695926974952
608 2833980877035
609 23245229340
610 1
611 171
612 13365
613 632502
614 20241900
615 463372812
616 7827690717
617 99245228940
618 951400853793
619 6895812389895
620 37540129888404
621 151459294750344
622 443461899043800
623 913812438120120
624 1268359796416725
625 1112883434275320
626 561238628492295
627 139674771796725
628 13036312034361
629 244074908070
630 1
631 174
632 13860
633 669708
634 21928725
635 514858680
636 8945932248
637 117058475160
638 1162823265747
639 8776488496230
640 50053506517872
641 213164933352336
642 665192848565700
643 1479505852194480
644 2254861860296400
645 2225766868550640
646 1309556799815355
647 403504896301650
648 52145248137444
649 1789882659180
650 3486784401
651 1
652 177
653 14364
654 708345
655 23718825
656 570821580
657 10194201864
658 137543708313
659 1414244512395
660 11099676627585
661 66199798942992
662 296908300026468
663 984485415877236
664 2353759310309400
665 3916339020514800
666 4312423307816865
667 2921319014972715
668 1089463220014455
669 186233029062300
670 10291825290285
671 73222472421
672 1
673 180
674 14877
675 748440
676 25616331
677 631547280
678 11584320300
679 161026780464
680 1711980199215
681 13953879188964
682 86887236112677
683 409528689691680
684 1438863300128268
685 3684145007440800
686 6657776334875160
687 8117502697067040
688 6259969317798675
689 2773179105491340
690 605257344452475
691 49400761393368
692 805447196631
693 1
694 183
695 15399
696 790020
697 27625455
698 697333455
699 13128896340
700 187864577208
701 2063155624695
702 17442348986205
703 113216701601367
704 559689209245296
705 2078358100185276
706 5679723553137900
707 11096293891458600
708 14882088277956240
709 12937269923450595
710 6701849504937405
711 1815772033357425
712 205836505805700
713 6175095174171
714 10460353203
715 1
716 186
717 15930
718 833112
719 29750490
720 768489930
721 14841361080
722 218447182800
723 2475786749634
724 21685082523390
725 146515731484122
726 758288606074272
727 2969083000264680
728 8633179800769608
729 18157571822386800
730 26631105339500640
731 25874539846901190
732 15465806549855550
733 5084161693400790
734 764535592992600
735 37050571045026
736 230127770466
737 1
738 189
739 16470
740 877743
741 31995810
742 845338923
743 16736002920
744 253200143700
745 2958867091026
746 26821023121035
747 188377369051014
748 1018950314412303
749 4197669069339720
750 12949769701154412
751 29210006844709200
752 46604434344126120
753 50227047938102310
754 34245714503251575
755 13403699009874810
756 2580307626350025
757 185252855225130
758 2646469360359
759 1
760 192
761 17019
762 923940
763 34365870
764 928215288
765 18828003285
766 292586832720
767 3522460822650
768 33010489995120
769 240704416009629
770 1358600419216404
771 5876736697075608
772 19184844001710240
773 46249177504122900
774 79893316018501920
775 94873312771971030
776 73057524273603360
777 33509247524687025
778 8027623726422300
779 802762372642230
780 21171754882872
781 31381059609
782 1
783 195
784 17577
785 971730
786 36865206
787 1017466758
788 21133473075
789 337110915960
790 4177802371050
791 40437850244022
792 305759663579799
793 1798147613668770
794 8151602515298424
795 28092093002504280
796 72148716906431724
797 134366031485662320
798 174766628790472950
799 150681143814306930
800 79906667174253675
801 23280108806624670
802 3096369151620030
803 132323468017950
804 721764371007
805 1
806 198
807 18144
808 1021140
809 39498435
810 1113454188
811 23669489844
812 387318924720
813 4937402802150
814 49314451517100
815 386222732942904
816 2363279720821812
817 11208453458535333
818 40685100210523440
819 110998026009894960
820 221996052019789920
821 314579931822851310
822 301362287628613860
823 182643810684008400
824 63491205836249100
825 10837292030670105
826 688082033693340
827 8661172452084
828 1
829 201
830 18720
831 1072197
832 42270255
833 1216551798
834 26454135708
835 443802934575
836 5815163300310
837 59881833985050
838 485254202928264
839 3085392968850699
840 15284254716184545
841 58315310301750264
842 168552558015025680
843 360743584532158620
844 554259879878357070
845 585982225944526950
846 401816383504818480
847 164018948410310175
848 34920163209937005
849 3096369151620030
850 72176437100700
851 94143178827
852 1
853 204
854 19305
855 1124928
856 45185445
857 1327147416
858 29506535982
859 507203353800
860 6826496048190
861 72415241098200
862 606567753660330
863 4002671959590096
864 20678697557190855
865 82770117847645536
866 252828837022538520
867 577189735251453792
868 957357974335344030
869 1110282112315945800
870 853859814947739270
871 403738949933071200
872 104760489629811015
873 12385476606480120
874 469146841154550
875 2259436291848
876 1
877 207
878 19899
879 1179360
880 48248865
881 1445642721
882 32846898546
883 578211823332
884 7988452822350
885 87227449504650
886 754511108211630
887 5161340158418808
888 27768536719656291
889 116395478223251535
890 374884137654108840
891 910183813281138672
892 1623346130394713790
893 2054021907784499730
894 1757946677833580850
895 951670381985096400
896 295234107138558315
897 44897352698490435
898 2533392942234570
899 28242953648100
900 1
901 210
902 20502
903 1235520
904 51465456
905 1572453486
906 36496553940
907 657574230456
908 9319861626075
909 104672939405580
910 934156610166780
911 6617102767203600
912 37024715626208388
913 162248242371805170
914 549830068559359632
915 1415841487326215712
916 2705576883991189650
917 3716801547419570940
918 3515893355667161700
919 2157119532499551840
920 787290952369488840
921 149657842328301450
922 11822500397094660
923 244772264950200
924 282429536481
925 1
926 213
927 21114
928 1293435
929 54840240
930 1708009821
931 40477996188
932 746093838402
933 10841471687475
934 125152427550150
935 1151402333461380
936 8436806028184590
937 49032731504978676
938 224284335043377735
939 798140422102296240
940 2174327998393831272
941 4437146089745551026
942 6588875470425603030
943 6846739692614999100
944 4718698977342769650
945 1998507802168702440
946 463939311217734495
947 48978930216535020
948 1652212788413850
949 7060738412025
950 1
951 216
952 21735
953 1353132
954 58378320
955 1852756416
956 44814924351
957 844634534040
958 12576107157471
959 149117786017200
960 1413084681975330
961 10700339352819480
962 64516751980235100
963 307589945202346608
964 1147326856772050845
965 3298980411356157792
966 7167697529588967042
967 11458913861609744400
968 13008805415968498290
969 9992539010843512200
970 4853518948123991640
971 1349641632633409440
972 183670988312006325
973 9252391615117560
974 91789599356325
975 1
976 219
977 22365
978 1414638
979 62084880
980 2007152784
981 49532284809
982 954124195860
983 14548829848839
984 177077370895425
985 1727103500192070
986 13502809183319820
987 84368060281845900
988 418664092080971772
989 1634071583887466355
990 4948470617034236688
991 11415221991567614178
992 19575644513583313350
993 24159210058227211110
994 20540219077844997300
995 11324877545622647160
996 3711514489741875960
997 632644515296910675
998 44719892806401540
999 826106394206925
1000 847288609443