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 385
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 12288
33 1089
34 1540
35 1617
36 2376
37 1441
38 1444
39 873
40 6336
41 641
42 1764
43 1849
44 2904
45 3267
46 2116
47 2209
48 13824
49 2695
50 3700
51 3465
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 65536
65 3201
66 4356
67 4489
68 9240
69 4761
70 6468
71 5041
72 19008
73 5761
74 5764
75 8325
76 8664
77 5929
78 3492
79 6241
80 50688
81 25515
82 2564
83 6889
84 10584
85 12705
86 7396
87 10089
88 23232
89 7041
90 13068
91 4753
92 12696
93 8649
94 8836
95 11913
96 110592
97 14593
98 10780
99 11979
100 22200
101 10401
102 13860
103 10609
104 18624
105 14553
106 8324
107 11449
108 33048
109 11233
110 15972
111 12969
112 75264
113 2689
114 12996
115 17457
116 26904
117 9603
118 13924
119 18865
120 57024
121 15851
122 17284
123 5769
124 23064
125 35625
126 19404
127 16129
128 393216
129 16641
130 12804
131 17161
132 26136
133 17689
134 17956
135 45441
136 73920
137 36993
138 19044
139 19321
140 38808
141 19881
142 20164
143 11737
144 152064
145 36993
146 23044
147 24255
148 34584
149 20129
150 33300
151 22801
152 69312
153 38115
154 23716
155 31713
156 20952
157 21217
158 24964
159 18729
160 405504
161 25921
162 102060
163 26569
164 15384
165 35937
166 27556
167 27889
168 84672
169 18421
170 50820
171 35739
172 44376
173 34401
174 40356
175 45325
176 185856
177 31329
178 28164
179 32041
180 78408
181 36001
182 19012
183 38889
184 101568
185 47553
186 34596
187 46585
188 53016
189 67473
190 47652
191 36481
192 589824
193 29185
194 58372
195 28809
196 64680
197 39201
198 47916
199 39601
200 177600
201 40401
202 41604
203 54929
204 83160
205 21153
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 51849
220 95832
221 37345
222 51876
223 49729
224 602112
225 91575
226 10756
227 51529
228 77976
229 45601
230 69828
231 53361
232 215232
233 48257
234 38412
235 72897
236 83544
237 56169
238 75460
239 57121
240 456192
241 36481
242 63404
243 583929
244 103704
245 88935
246 23076
247 35017
248 184512
249 62001
250 142500
251 63001
252 116424
253 64009
254 64516
255 114345
256 2621440
257 153601
258 66564
259 70609
260 76824
261 110979
262 68644
263 69169
264 209088
265 68673
266 70756
267 63369
268 107736
269 79329
270 181764
271 73441
272 591360
273 42777
274 147972
275 111925
276 114264
277 81697
278 77284
279 95139
280 310464
281 76161
282 79524
283 80089
284 120984
285 107217
286 46948
287 31409
288 1216512
289 115889
290 147972
291 131337
292 138264
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 152460
307 94249
308 142296
309 95481
310 126852
311 96721
312 167616
313 44929
314 84868
315 160083
316 149784
317 93537
318 74916
319 135641
320 2162688
321 103041
322 103684
323 138985
324 612360
325 89725
326 106276
327 101097
328 123072
329 108241
330 143748
331 109561
332 165336
333 142659
334 111556
335 148137
336 677376
337 115585
338 73684
339 24201
340 304920
341 116281
342 142956
343 232897
344 355008
345 157113
346 137604
347 120409
348 242136
349 125281
350 181300
351 133569
352 1486848
353 143617
354 125316
355 166353
356 168984
357 169785
358 128164
359 128881
360 627264
361 136819
362 144004
363 142659
364 114072
365 190113
366 155556
367 134689
368 812544
369 63459
370 190212
371 101969
372 207576
373 133921
374 186340
375 320625
376 424128
377 108737
378 269892
379 143641
380 285912
381 145161
382 145924
383 146689
384 3538944
385 195657
386 116740
387 183051
388 350232
389 164513
390 115236
391 203665
392 517440
393 154449
394 156804
395 205953
396 287496
397 142561
398 158404
399 159201
400 1420800
401 163201
402 161604
403 93217
404 249624
405 841995
406 219716
407 174361
408 665280
409 215425
410 84612
411 332937
412 254616
413 170569
414 209484
415 227337
416 1191936
417 173889
418 174724
419 175561
420 349272
421 164641
422 178084
423 218691
424 399552
425 356125
426 181476
427 211729
428 274776
429 105633
430 244068
431 185761
432 2115072
433 231553
434 188356
435 332937
436 269592
437 190969
438 207396
439 192721
440 766656
441 266805
442 149380
443 196249
444 311256
445 232353
446 198916
447 181161
448 3211264
449 182785
450 366300
451 77561
452 64536
453 205209
454 206116
455 156849
456 623808
457 65665
458 182404
459 530145
460 418968
461 195041
462 213444
463 214369
464 1721856
465 285417
466 193028
467 218089
468 230472
469 219961
470 291588
471 190953
472 668352
473 223729
474 224676
475 333925
476 452760
477 206019
478 228484
479 229441
480 3649536
481 139777
482 145924
483 233289
484 380424
485 481569
486 2335716
487 237169
488 829632
489 239121
490 355740
491 241081
492 138456
493 431585
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 457380
511 282289
512 10485760
513 497097
514 614404
515 350097
516 399384
517 267289
518 282436
519 309609
520 614592
521 341121
522 443916
523 273529
524 411864
525 407925
526 276676
527 369985
528 1672704
529 291479
530 274692
531 344619
532 424536
533 62177
534 253476
535 377817
536 861888
537 288369
538 317316
539 326095
540 1090584
541 315361
542 293764
543 324009
544 4730880
545 370689
546 171108
547 299209
548 887832
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 419265
562 304644
563 316969
564 477144
565 88737
566 320356
567 1250235
568 967872
569 154497
570 428868
571 326041
572 281688
573 328329
574 125636
575 489325
576 6488064
577 87553
578 463556
579 262665
580 887832
581 337561
582 525348
583 251801
584 1106112
585 316899
586 383108
587 344569
588 582120
589 346921
590 459492
591 352809
592 2213376
593 468865
594 666468
595 622545
596 483096
597 356409
598 205252
599 358801
600 1598400
601 355201
602 362404
603 444411
604 547224
605 523083
606 374436
607 368449
608 4435968
609 494361
610 570372
611 214273
612 914760
613 396577
614 376996
615 190377
616 1138368
617 404097
618 381924
619 383161
620 761112
621 728433
622 386884
623 345009
624 1340928
625 2453125
626 179716
627 393129
628 509208
629 554785
630 640332
631 398161
632 1198272
633 400689
634 374148
635 532257
636 449496
637 261415
638 542564
639 499059
640 12976128
641 506881
642 412164
643 413449
644 622104
645 549153
646 555940
647 418609
648 4898880
649 421201
650 358900
651 423801
652 637656
653 443361
654 404388
655 566313
656 984576
657 570339
658 432964
659 434281
660 862488
661 469921
662 438244
663 336105
664 1322688
665 583737
666 570636
667 593009
668 669336
669 447561
670 592548
671 522841
672 5419008
673 360193
674 462340
675 1273725
676 442104
677 459681
678 96804
679 715057
680 2439360
681 463761
682 465124
683 466489
684 857736
685 1220769
686 931588
687 410409
688 2840064
689 201857
690 628452
691 477481
692 825624
693 586971
694 481636
695 637593
696 1937088
697 246785
698 501124
699 434313
700 1087800
701 498401
702 534276
703 520201
704 7929856
705 656073
706 574468
707 509649
708 751896
709 481441
710 665412
711 617859
712 1351872
713 508369
714 679140
715 387321
716 768984
717 514089
718 515524
719 516961
720 5018112
721 519841
722 547276
723 328329
724 864024
725 1036925
726 570636
727 528529
728 912576
729 14821299
730 760452
731 711865
732 933336
733 497761
734 538756
735 800415
736 6500352
737 543169
738 253836
739 546121
740 1141272
741 315153
742 407876
743 552049
744 1660608
745 664257
746 535684
747 682011
748 1118040
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 887681
762 580644
763 550417
764 875544
765 1257795
766 586756
767 337657
768 23592960
769 706561
770 782628
771 1382409
772 700440
773 623777
774 732204
775 888925
776 2801856
777 635481
778 658052
779 231401
780 691416
781 609961
782 814660
783 1543617
784 4139520
785 700161
786 617796
787 619369
788 940824
789 622521
790 823812
791 131761
792 2299968
793 419137
794 570244
795 618057
796 950424
797 617697
798 636804
799 850465
800 11366400
801 697059
802 652804
803 697081
804 969624
805 855393
806 372868
807 713961
808 1996992
809 633473
810 3367980
811 657721
812 1318296
813 660969
814 697444
815 876777
816 5322240
817 667489
818 861700
819 470547
820 507672
821 715041
822 1331748
823 677329
824 2036928
825 1007325
826 682276
827 683929
828 1256904
829 642529
830 909348
831 735273
832 6356992
833 1037575
834 695556
835 920337
836 1048344
837 1323297
838 702244
839 703921
840 2794176
841 966309
842 658564
843 685449
844 1068504
845 607893
846 874764
847 776699
848 3196416
849 720801
850 1424500
851 762289
852 1088856
853 688417
854 846916
855 1179387
856 2198208
857 671105
858 422532
859 737881
860 1464408
861 282681
862 743044
863 744769
864 16920576
865 1135233
866 926212
867 1043001
868 1130136
869 755161
870 1331748
871 435433
872 2156736
873 1444707
874 763876
875 1745625
876 1244376
877 819937
878 770884
879 861993
880 6133248
881 190081
882 1067220
883 779689
884 896280
885 1033857
886 784996
887 786769
888 2490048
889 790321
890 929412
891 3087315
892 1193496
893 797449
894 724644
895 1057353
896 19267584
897 461817
898 731140
899 1077281
900 2197800
901 801185
902 310244
903 815409
904 516288
905 1188033
906 820836
907 822649
908 1236696
909 1029699
910 627396
911 829921
912 4990464
913 833569
914 262660
915 1283337
916 1094424
917 840889
918 2120580
919 844561
920 3351744
921 848241
922 780164
923 488977
924 1280664
925 1332925
926 857476
927 1050291
928 13774848
929 734977
930 1141668
931 972895
932 1158168
933 870489
934 872356
935 1537305
936 1843776
937 913537
938 879844
939 404361
940 1749528
941 940001
942 763812
943 339089
944 5346816
945 2226609
946 894916
947 896809
948 1348056
949 558817
950 1335700
951 841833
952 3622080
953 624513
954 824076
955 1203873
956 1370904
957 1220769
958 917764
959 1812657
960 19464192
961 952351
962 559108
963 1133451
964 875544
965 963105
966 933156
967 935089
968 3043392
969 1250865
970 1926276
971 942841
972 14014296
973 946729
974 948676
975 807525
976 6637056
977 772993
978 956484
979 851961
980 2134440
981 1112067
982 964324
983 966289
984 1107648
985 1293633
986 1726340
987 974169
988 840408
989 978121
990 1581228
991 982081
992 11808768
993 986049
994 988036
995 1306833
996 1488024
997 932257
998 996004
999 1984257
1000 6840000