100
955 795515 662663995 360944128
899 176204 351509 340068392
67 8844 1167408 143877824
522 334080 667638 69426531
207 64377 20021247 88716536
218 165680 125916800 517781627
31 23002 45973 25672375
229 138316 276403 12008989
650 50050 3853850 191102976
897 494247 272330097 69934528
286 203918 407550 649461896
377 127803 255229 614125000
274 161112 94733856 555412248
748 474232 947716 137388096
676 522548 403929604 433798093
772 541172 379361572 24897088
171 37962 75753 3048625
576 456768 362217024 114791256
703 442187 278135623 611960049
298 230354 460410 27000000
20 10620 5639220 426957777
658 308602 144734338 12812904
147 18816 37485 4096
170 31790 5944730 935441352
561 491997 431481369 2146689
224 175840 351456 470910952
942 844032 1687122 961504803
870 333210 127619430 117649
310 90520 180730 117649
93 37479 74865 36926037
115 94530 77703660 580093704
174 148248 296322 360944128
346 279914 226450426 208527857
1000 167000 333000 269586136
882 672084 512128008 311665752
85 52530 104975 110592
872 18312 35752 1000000
764 88624 176484 58863869
973 777427 1553881 15438249
17 5763 11509 195112000
614 295948 591282 15625
8 5272 3474248 73560059
963 612468 1223973 86938307
342 160740 75547800 565609283
921 456816 912711 275894451
96 57408 114720 362467097
672 109536 17854368 382657176
266 77938 22835834 359425431
246 184992 139113984 122763473
690 202860 405030 4173281
650 55250 109850 783777448
914 498130 271480850 1404928
162 30456 60750 36926037
617 569491 1138365 77308776
421 301015 601609 531441
666 141192 281718 907039232
74 35224 70374 292754944
427 276269 178746043 926859375
663 247962 92737788 38958219
248 229400 212195000 49836032
394 196212 392030 729000000
30 5100 867000 160989184
452 429400 858348 15625000
600 498600 414336600 72511713
25 14925 8910225 53157376
478 289668 175538808 63521199
745 343445 686145 40001688
433 31609 2307457 178453547
370 278240 556110 970299000
680 182240 48840320 286191179
788 596516 451562612 23887872
861 631974 463868916 799178752
515 426420 852325 146363183
41 34276 28654736 13651919
897 419796 838695 61162984
964 892664 1784364 4826809
170 126650 253130 24897088
782 719440 1438098 178453547
941 457326 913711 584277056
649 380314 222864004 523606616
218 109872 55375488 300763000
884 544544 335439104 64000
214 94802 41997286 233744896
210 119910 239610 244140625
129 15738 1920036 322828856
265 37630 74995 167284151
985 869755 1738525 879217912
499 28942 1678636 61629875
131 116459 103532051 833237621
256 178688 124724224 236029032
209 75449 150689 841232384
946 537328 305202304 672221376
71 37843 20170319 257259456
392 102704 26908448 76225024
245 169540 117321680 27543608
196 26264 3519376 343
745 356855 712965 726572699
509 111471 24412149 10648000
258 230394 460530 129554216
125 40625 13203125 51064811