1 1
2 4
3 9
4 24
5 33
6 36
7 49
8 192
9 99
10 132
11 121
12 216
13 97
14 196
15 297
16 1536
17 193
18 396
19 361
20 792
21 441
22 484
23 529
24 1728
25 925
26 388
27 1377
28 1176
29 1121
30 1188
31 961
32 6144
33 1089
34 772
35 1617
36 2376
37 1441
38 1444
39 873
40 6336
41 481
42 1764
43 1849
44 2904
45 3267
46 2116
47 2209
48 13824
49 2695
50 3700
51 1737
52 2328
53 2081
54 5508
55 3993
56 9408
57 3249
58 4484
59 3481
60 7128
61 4321
62 3844
63 4851
64 28672
65 3201
66 4356
67 4489
68 4632
69 4761
70 6468
71 5041
72 19008
73 6625
74 5764
75 8325
76 8664
77 5929
78 3492
79 6241
80 50688
81 25515
82 1924
83 6889
84 10584
85 6369
86 7396
87 10089
88 23232
89 5281
90 13068
91 4753
92 12696
93 8649
94 8836
95 11913
96 55296
97 4225
98 10780
99 11979
100 22200
101 10401
102 6948
103 10609
104 18624
105 14553
106 8324
107 11449
108 33048
109 11233
110 15972
111 12969
112 75264
113 17473
114 12996
115 17457
116 26904
117 9603
118 13924
119 9457
120 57024
121 15851
122 17284
123 4329
124 23064
125 35625
126 19404
127 16129
128 163840
129 16641
130 12804
131 17161
132 26136
133 17689
134 17956
135 45441
136 37056
137 27745
138 19044
139 19321
140 38808
141 19881
142 20164
143 11737
144 152064
145 36993
146 26500
147 24255
148 34584
149 20129
150 33300
151 22801
152 69312
153 19107
154 23716
155 31713
156 20952
157 21217
158 24964
159 18729
160 202752
161 25921
162 102060
163 26569
164 11544
165 35937
166 27556
167 27889
168 84672
169 18421
170 25476
171 35739
172 44376
173 34401
174 40356
175 45325
176 185856
177 31329
178 21124
179 32041
180 78408
181 36001
182 19012
183 38889
184 101568
185 47553
186 34596
187 23353
188 53016
189 67473
190 47652
191 36481
192 258048
193 45313
194 16900
195 28809
196 64680
197 39201
198 47916
199 39601
200 177600
201 40401
202 41604
203 54929
204 41688
205 15873
206 42436
207 52371
208 148992
209 43681
210 58212
211 44521
212 49944
213 45369
214 45796
215 61017
216 264384
217 47089
218 44932
219 59625
220 95832
221 18721
222 51876
223 49729
224 301056
225 91575
226 69892
227 51529
228 77976
229 45601
230 69828
231 53361
232 215232
233 36193
234 38412
235 72897
236 83544
237 56169
238 37828
239 57121
240 456192
241 79681
242 63404
243 229635
244 103704
245 88935
246 17316
247 35017
248 184512
249 62001
250 142500
251 63001
252 116424
253 64009
254 64516
255 57321
256 1048576
257 64513
258 66564
259 70609
260 76824
261 110979
262 68644
263 69169
264 209088
265 68673
266 70756
267 47529
268 107736
269 79329
270 181764
271 73441
272 296448
273 42777
274 110980
275 111925
276 114264
277 81697
278 77284
279 95139
280 310464
281 70561
282 79524
283 80089
284 120984
285 107217
286 46948
287 23569
288 608256
289 60401
290 147972
291 38025
292 159000
293 95777
294 97020
295 114873
296 276672
297 166617
298 80516
299 51313
300 199800
301 90601
302 91204
303 93609
304 554496
305 142593
306 76428
307 94249
308 142296
309 95481
310 126852
311 96721
312 167616
313 73633
314 84868
315 160083
316 149784
317 93537
318 74916
319 135641
320 946176
321 103041
322 103684
323 69673
324 612360
325 89725
326 106276
327 101097
328 92352
329 108241
330 143748
331 109561
332 165336
333 142659
334 111556
335 148137
336 677376
337 95425
338 73684
339 157257
340 152856
341 116281
342 142956
343 232897
344 355008
345 157113
346 137604
347 120409
348 242136
349 125281
350 181300
351 133569
352 743424
353 88705
354 125316
355 166353
356 126744
357 85113
358 128164
359 128881
360 627264
361 136819
362 144004
363 142659
364 114072
365 218625
366 155556
367 134689
368 812544
369 47619
370 190212
371 101969
372 207576
373 133921
374 93412
375 320625
376 424128
377 108737
378 269892
379 143641
380 285912
381 145161
382 145924
383 146689
384 1474560
385 195657
386 181252
387 183051
388 101400
389 164513
390 115236
391 102097
392 517440
393 154449
394 156804
395 205953
396 287496
397 142561
398 158404
399 159201
400 1420800
401 158401
402 161604
403 93217
404 249624
405 841995
406 219716
407 174361
408 333504
409 174625
410 63492
411 249705
412 254616
413 170569
414 209484
415 227337
416 595968
417 173889
418 174724
419 175561
420 349272
421 164641
422 178084
423 218691
424 399552
425 178525
426 181476
427 211729
428 274776
429 105633
430 244068
431 185761
432 2115072
433 143425
434 188356
435 332937
436 269592
437 190969
438 238500
439 192721
440 766656
441 266805
442 74884
443 196249
444 311256
445 174273
446 198916
447 181161
448 1404928
449 220417
450 366300
451 58201
452 419352
453 205209
454 206116
455 156849
456 623808
457 151393
458 182404
459 265761
460 418968
461 195041
462 213444
463 214369
464 1721856
465 285417
466 144772
467 218089
468 230472
469 219961
470 291588
471 190953
472 668352
473 223729
474 224676
475 333925
476 226968
477 206019
478 228484
479 229441
480 1824768
481 139777
482 318724
483 233289
484 380424
485 139425
486 918540
487 237169
488 829632
489 239121
490 355740
491 241081
492 103896
493 216353
494 140068
495 395307
496 1476096
497 247009
498 248004
499 249001
500 855000
501 251001
502 252004
503 253009
504 931392
505 343233
506 256036
507 165789
508 387096
509 264161
510 229284
511 324625
512 4194304
513 497097
514 258052
515 350097
516 399384
517 267289
518 282436
519 309609
520 614592
521 305761
522 443916
523 273529
524 411864
525 407925
526 276676
527 185473
528 1672704
529 291479
530 274692
531 344619
532 424536
533 46657
534 190116
535 377817
536 861888
537 288369
538 317316
539 326095
540 1090584
541 315361
542 293764
543 324009
544 1185792
545 370689
546 171108
547 299209
548 665880
549 427779
550 447700
551 404681
552 914112
553 305809
554 326788
555 427977
556 463704
557 289121
558 380556
559 179353
560 2483712
561 210177
562 282244
563 316969
564 477144
565 576609
566 320356
567 1250235
568 967872
569 279457
570 428868
571 326041
572 281688
573 328329
574 94276
575 489325
576 2838528
577 329473
578 241604
579 407817
580 887832
581 337561
582 152100
583 251801
584 1272000
585 316899
586 383108
587 344569
588 582120
589 346921
590 459492
591 352809
592 2213376
593 433345
594 666468
595 312081
596 483096
597 356409
598 205252
599 358801
600 1598400
601 343201
602 362404
603 444411
604 547224
605 523083
606 374436
607 368449
608 2217984
609 494361
610 570372
611 214273
612 458568
613 396577
614 376996
615 142857
616 1138368
617 450913
618 381924
619 383161
620 761112
621 728433
622 386884
623 258769
624 1340928
625 2453125
626 294532
627 393129
628 509208
629 278113
630 640332
631 398161
632 1198272
633 400689
634 374148
635 532257
636 449496
637 261415
638 542564
639 499059
640 5406720
641 314881
642 412164
643 413449
644 622104
645 549153
646 278692
647 418609
648 4898880
649 421201
650 358900
651 423801
652 637656
653 443361
654 404388
655 566313
656 738816
657 655875
658 432964
659 434281
660 862488
661 469921
662 438244
663 168489
664 1322688
665 583737
666 570636
667 593009
668 669336
669 447561
670 592548
671 522841
672 2709504
673 545665
674 381700
675 1273725
676 442104
677 459681
678 629028
679 207025
680 1222848
681 463761
682 465124
683 466489
684 857736
685 915585
686 931588
687 410409
688 2840064
689 201857
690 628452
691 477481
692 825624
693 586971
694 481636
695 637593
696 1937088
697 92833
698 501124
699 325737
700 1087800
701 498401
702 534276
703 520201
704 3469312
705 656073
706 354820
707 509649
708 751896
709 481441
710 665412
711 617859
712 1013952
713 508369
714 340452
715 387321
716 768984
717 514089
718 515524
719 516961
720 5018112
721 519841
722 547276
723 717129
724 864024
725 1036925
726 570636
727 528529
728 912576
729 2421009
730 874500
731 356857
732 933336
733 497761
734 538756
735 800415
736 3250176
737 543169
738 190476
739 546121
740 1141272
741 315153
742 407876
743 552049
744 1660608
745 664257
746 535684
747 682011
748 560472
749 561001
750 1282500
751 564001
752 3393024
753 567009
754 434948
755 752433
756 1619352
757 586657
758 574564
759 576081
760 2287296
761 665761
762 580644
763 550417
764 875544
765 630531
766 586756
767 337657
768 9437184
769 476161
770 782628
771 580617
772 1087512
773 623777
774 732204
775 888925
776 811200
777 635481
778 658052
779 173641
780 691416
781 609961
782 408388
783 1543617
784 4139520
785 700161
786 617796
787 619369
788 940824
789 622521
790 823812
791 856177
792 2299968
793 419137
794 570244
795 618057
796 950424
797 617697
798 636804
799 426337
800 5683200
801 522819
802 633604
803 801625
804 969624
805 855393
806 372868
807 713961
808 1996992
809 630241
810 3367980
811 657721
812 1318296
813 660969
814 697444
815 876777
816 2668032
817 667489
818 698500
819 470547
820 380952
821 715041
822 998820
823 677329
824 2036928
825 1007325
826 682276
827 683929
828 1256904
829 642529
830 909348
831 735273
832 2781184
833 520135
834 695556
835 920337
836 1048344
837 1323297
838 702244
839 703921
840 2794176
841 966309
842 658564
843 635049
844 1068504
845 607893
846 874764
847 776699
848 3196416
849 720801
850 714100
851 762289
852 1088856
853 688417
854 846916
855 1179387
856 2198208
857 585505
858 422532
859 737881
860 1464408
861 212121
862 743044
863 744769
864 8460288
865 1135233
866 573700
867 543609
868 1130136
869 755161
870 1331748
871 435433
872 2156736
873 418275
874 763876
875 1745625
876 1431000
877 819937
878 770884
879 861993
880 6133248
881 644161
882 1067220
883 779689
884 449304
885 1033857
886 784996
887 786769
888 2490048
889 790321
890 697092
891 3087315
892 1193496
893 797449
894 724644
895 1057353
896 8028160
897 461817
898 881668
899 1077281
900 2197800
901 401633
902 232804
903 815409
904 3354816
905 1188033
906 820836
907 822649
908 1236696
909 1029699
910 627396
911 829921
912 4990464
913 833569
914 605572
915 1283337
916 1094424
917 840889
918 1063044
919 844561
920 3351744
921 848241
922 780164
923 488977
924 1280664
925 1332925
926 857476
927 1050291
928 6887424
929 991105
930 1141668
931 972895
932 868632
933 870489
934 872356
935 770649
936 1843776
937 984673
938 879844
939 662697
940 1749528
941 940001
942 763812
943 254449
944 5346816
945 2226609
946 894916
947 896809
948 1348056
949 642625
950 1335700
951 841833
952 1815744
953 833953
954 824076
955 1203873
956 1370904
957 1220769
958 917764
959 1359505
960 8515584
961 952351
962 559108
963 1133451
964 1912344
965 1495329
966 933156
967 935089
968 3043392
969 627057
970 557700
971 942841
972 5511240
973 946729
974 948676
975 807525
976 6637056
977 1136065
978 956484
979 639001
980 2134440
981 1112067
982 964324
983 966289
984 831168
985 1293633
986 865412
987 974169
988 840408
989 978121
990 1581228
991 982081
992 5904384
993 986049
994 988036
995 1306833
996 1488024
997 932257
998 996004
999 1984257
1000 6840000