AA = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 397210877, 794421754, 1588843508, 3177687016, 2457617613, 1017478807, 2034957614, 172158809, 344317618, 688635236, 1377270472, 2754540944, 1611325469, 3222650938, 2547545457, 1197334495, 2394668990, 891581561, 1783163122], [3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 2664840365, 199008257, 597024771, 1791074313, 1475466520, 528643141, 1585929423, 860031850, 2580095550, 3842530231, 3732077855, 3400720727, 2406649343, 3322191610, 2171061992, 2615429557, 50775833, 152327499, 456982497, 1370947491, 215086054, 645258162, 1935774486, 1909567039, 1830944698, 1595077675, 887476606, 2662429818, 191776616, 575329848], [4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 397210877, 1588843508, 2457617613, 2034957614, 344317618, 1377270472, 1611325469, 2547545457, 2394668990, 1783163122, 3234896069, 1246315019, 1087503657, 452258209, 1809032836, 3338374925, 1660230443, 2743165353, 3177148574, 1015325039, 163543737, 654174948, 2616699792, 2671286330, 2889632482, 3763017090, 3358799103, 1741927155, 3069952201, 586539547, 2346158188, 1589119914, 2458723237, 2039380110, 362007602], [5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 2205759206, 3233283192, 575390284, 2876951420, 2691487843, 1764169958, 1025336952, 1228928341, 2246885286, 3438913592, 1603542284, 222198582, 1110992910, 1657208131, 490527817, 2452639085, 569926168, 2849630840, 2554884943, 1081155458, 1508020871, 3642347936, 2620714004, 1410300763, 3153747396, 177711304, 888556520, 545026181, 2725130905, 1932385268, 1866413502, 1536554672, 3785016941, 3334059029, 1079269469, 1498590926, 3595198211], [6, 36, 216, 1296, 7776, 46656, 279936, 1679616, 10077696, 60466176, 362797056, 2176782336, 1367424759, 409035716, 2454214296, 3032016519, 2601073438, 15414952, 92489712, 554938272, 3329629632, 488995697, 2933974182, 2012819416, 383647239, 2301883434, 2118031347, 1014918825, 2191756531, 1457269929, 948106736, 1790883997, 2949791144, 2107721188, 953057871, 1820590807, 3128032004, 3177166348, 3471972412, 1343052377, 262801424, 1576808544, 1665338426, 2196517718, 1485837051, 1119509468, 2819300389, 1324776658, 153147110, 918882660], [7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607, 282475249, 1977326743, 2148017944, 3342856351, 13455943, 94191601, 659341207, 717632030, 1125667791, 84161699, 589131893, 226166832, 1583167824, 3286661930, 3517851415, 1238421391, 873436899, 2216301874, 3820843861, 3359368513, 129041077, 903287539, 2425256354, 1385768802, 1904868776, 1640812175, 3690172387, 2444668195, 1521651689, 2856048985, 503560800, 3524925600, 1287940686, 1220071964, 744990910, 1317179951, 1424746819, 2177714895, 3550735008, 1468606542, 2484732956], [8, 64, 512, 4096, 32768, 262144, 2097152, 16777216, 134217728, 1073741824, 794421754, 2457617613, 172158809, 1377270472, 3222650938, 2394668990, 3566326244, 1246315019, 2175007314, 1809032836, 2778993431, 2743165353, 2456540729, 163543737, 1308349896, 2671286330, 1881508545, 3358799103, 3483854310, 586539547, 794559957, 2458723237, 181003801, 1448030408, 3788730426, 3025548475, 817849286, 2645037869, 1671520857, 1678897599, 1737911535, 2210023023, 2089158508, 1122242388, 1182426266, 1663897290, 1617909063, 1250003247, 2204513138, 2045079428], [9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489, 3486784401, 199008257, 1791074313, 528643141, 860031850, 3842530231, 3400720727, 3322191610, 2615429557, 152327499, 1370947491, 645258162, 1909567039, 1595077675, 2662429818, 575329848, 1280212213L, 3726397079, 2355522359, 1710919136, 3705002967, 2162975351L, 3875752483L, 3699720995L, 2115437603L, 3447912751L, 3746919826L, 2540227082L, 3373261643L, 3075059854L, 391243753L, 3521193777L, 508692641L, 680477350L, 2226539731L, 550075484L, 1052922937L, 1680793595L, 3433873098L, 3620562949L, 1403015189L], [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 2204487162, 2556089525, 2174356736, 2254785265, 3059070555, 3306410617, 1882054818, 3229522504, 1113173688, 3336224042, 2180189068, 2313108585, 3642303755, 1343229779, 1739028533, 1799259654, 2401570864, 629170126, 2393944841, 552909896, 1631342541, 722399734, 3326240921, 2080357858, 1314796485, 1454695593, 2853686673, 1252571797, 832448713, 528974292, 1391986501, 2226595753, 2777175435, 487459417, 976837751, 1972864672, 239864625L, 2398646250L, 599923986, 2101483441L, 1526052315], [11, 121, 1331, 14641, 161051, 1771561, 19487171, 214358881, 2357947691, 2550886087, 775452024, 734459426, 283540848, 3118949328, 3126391256, 3208252464, 210969333, 2320662663, 2140750779, 161720055, 1778920605, 79344560, 872790160, 1805178922, 368186047, 152290098, 1675191078, 2836076182, 14786650, 162653150L, 1789184650L, 192249055L, 2114739605L, 3773353560L, 2529324970L, 538279737L, 2023320688L, 2767745473L, 3160905270L, 3587906618L, 489408608L, 1485738269L, 752095283L, 477535275L, 1355131606L, 3213178409L, 265154728L, 2916702008L, 901670736L, 2122865258L], [12, 144, 1728, 20736, 248832, 2985984, 35831808, 429981696, 1262023933, 3451017939, 2434651078, 1931518003, 3689433941, 1397886683, 1183614520, 2510104983, 2836964863, 2861527004, 3156272696, 2795464581, 2363523620, 1077988507, 1242592827, 3217844667, 3534328233, 3434374606, 2234931082, 3432634470, 2214049450L, 3182054886, 3104850861, 2178402561, 2754292218, 1869455264, 2944681073, 256365105, 3076381260, 1836767349, 2552426093, 3344818183, 1160254006, 2229778815, 3370807266, 1472123002, 2074450348, 1506865662, 2491362268, 2612052283, 162576044, 1950912528], [13, 169, 2197, 28561, 371293, 4826809, 62748517, 815730721, 2808986535, 1437017184, 3090197716, 1195006118, 3841810277, 3170456573, 2238371259, 1814531434, 202370128, 2630811664, 3018500280, 262939450, 3418212850, 1561446441, 810021638, 2734768456, 472182157, 2240611622, 1843656153, 580991475, 3655132756, 743648800, 1871921562, 948441792, 636474039, 478649669, 2324689278, 2936665681, 3096846082, 1281434876, 1067627712, 2185890999, 1132288054, 3026475445, 366616595, 868259316, 3491858270, 2518836901, 1562828361, 827986598, 2968312936, 3508260397], [14, 196, 2744, 38416, 537824, 7529536, 105413504, 1475789056, 1172264689, 820679970, 3694006742, 1045260941, 2940383917, 2187810648, 3345054139, 57680918, 807532852, 3509947090, 2366182232, 1944499896, 3836460030, 3039606973, 3576933432, 3303991020, 3380553671, 554674366, 3867684705, 3476752423, 1901456894, 3233858002, 2398691419, 2399628514, 2412747844, 2596418464, 1270050725, 2189684474, 3371287703, 424950814, 2051554977, 1437474745, 635864335, 1106587852, 3798960671, 2514615947, 124815487, 1747416818, 1077296938, 3388887875, 671353222, 1603432270], [15, 225, 3375, 50625, 759375, 11390625, 170859375, 2562890625, 3363551604, 3680197032, 634365614, 1719971372, 2413032066, 1115673219, 1144072609, 1570063459, 164413371, 2466200565, 1913200704, 1413715627, 1716952310, 2367746136, 436384269, 2648007616, 742550050, 3342737912, 3367991652, 3746797752, 1633376414, 1114107696, 1120589764, 1217820784, 2676286084, 1166727070, 1909880374, 1363910677, 969878060, 2854901643, 3845960455, 3120816959, 39177357, 587660355, 1019392487, 3597618048, 3293437273, 2628482067, 449666815, 2847245806, 3731122900, 1398253634], [16, 256, 4096, 65536, 1048576, 16777216, 268435456, 397210877, 2457617613, 344317618, 1611325469, 2394668990, 3234896069, 1087503657, 1809032836, 1660230443, 3177148574, 163543737, 2616699792, 2889632482, 3358799103, 3069952201, 2346158188, 2458723237, 362007602, 1894365213, 3025548475, 1635698572, 2784638638, 1678897599, 3475823070, 1044579254, 1122242388, 2364852532, 2757832741, 1250003247, 511269857, 384804874, 2259121565, 1066137269, 1467170628, 88191534, 1411064544, 3088250609, 2638932716, 3245359266, 1254914809, 589854849, 1642164746, 2888097422], [17, 289, 4913, 83521, 1419857, 24137569, 410338673, 3078001022, 1655183927, 853831826, 2821871785, 1198743317, 889854294, 3434253741, 3813723731, 2469200723L, 2998848101L, 309584270L, 1365176171L, 3719212812L, 862515100L, 2969487443L, 3708209503L, 675458847L, 3687287561L, 319785833L, 1538602742L, 2769708100L, 311960672L, 1405575005L, 508236571L, 844508869L, 2663381516L, 2402165163L, 1859243581L, 425089525L, 3328765506L, 2020423736L, 3165152160L, 3136753273L, 2653972194L, 2242206689L, 3037705942L, 970167567L, 901822963L, 3637721114L, 3374912653L, 2804925235L, 910651967L, 3787814182L], [18, 324, 5832, 104976, 1889568, 34012224, 612220032, 3224447738, 3471469418, 122346820, 2202242760, 662805490, 237229563, 372375715, 2805006451, 3717039090L, 644844497L, 3811688108L, 2348526821L, 3295918588L, 860188299L, 3790120125L, 1960303127L, 205648515L, 3701673270L, 368259737L, 2730918847L, 2383462218L, 26999315L, 485987670L, 952265222L, 1549748320L, 611174827L, 3205634048L, 3132822998L, 1822224098L, 1617982412L, 1839388483L, 1926941342L, 3502892804L, 687967768L, 690150567L, 729440949L, 1436667825L, 2473482336L, 1647361439L, 2368210969L, 3650233252L, 3340095832L, 1655378691L], [19, 361, 6859, 130321, 2476099, 47045881, 893871739, 1392537365, 3071671421, 3793167133, 1910559985, 1220831944, 3707024841, 273856437, 1305515884, 1418263282, 3560463844, 1386953913, 2965585833, 1777540961, 2591226907, 2460234205, 3869129286, 3353840892, 1358874244, 2432072122, 3334049709, 982841767, 3082967897, 110043758, 2090831402, 748232448, 2523147255, 1166720817, 2678913428, 228521685, 444155596, 643443486, 532156977, 2315469725, 1118604166, 1764697059, 2347192769, 1721342002, 1523446686, 1661192101, 380598567, 3333616354, 974608022, 2926526742], [20, 400, 8000, 160000, 3200000, 64000000, 1280000000, 2213461486, 1393909111, 593887287, 184476483, 3689529660, 3630977658, 2459937618, 2425675332, 1740429612, 3626540888, 2371202218, 650967332, 1326077383, 3135009146, 336080216, 2823847901, 1908368154, 3087555309, 3284759895, 3331095196, 360044797, 3303139521, 3698687716, 3814138778, 2225403599, 1632751371, 1472976068, 2175226427, 629207931, 890889363, 2226761584, 1659911071, 2016170068, 1345837170, 3530204886, 444482178, 1094130722, 2393832345, 1103569872, 2582615345, 981473453, 140686965, 2813739300], [21, 441, 9261, 194481, 4084101, 85766121, 1801088541, 2743051590, 3035493524, 1381261300, 1722192367, 1086231936, 3322088561, 3502000658, 3382398276, 870748254, 2694687658, 2019850952, 3439305802, 2065806300, 506611691, 2843332673, 1243639848, 2729898294, 2759274308, 3376170602, 739967100, 3846039843, 2811708323, 579528498, 476829201, 2217900383, 3700587434, 3654964153, 2696875252, 2065790426, 506278337, 2836332239, 1096630734, 3540463319, 292357738, 2241756079, 303800631, 2482056832, 1452360025, 3215265592, 1258718309, 3046545975, 1613362771, 2698566839], [22, 484, 10648, 234256, 5153632, 113379904, 2494357888, 307283670, 2862484321, 610552358, 1738882619, 3175609847, 3601557511, 1279136862, 856716031, 3256727006, 1488378590, 1562277628, 3188056464, 3875383085, 3405543071, 864575601, 3429637546, 1394654051, 3398094189L, 700700197, 3722135077, 34086895L, 749911690L, 907031504, 465910993, 2454529008L, 3328804729L, 3074088496L, 1368087789L, 2813636425L, 3433655065L, 1483039469L, 1444816966L, 603921900L, 1593012543L, 3864224594L, 3160056269L, 3259378795L, 1546717948L, 2845743504L, 242254384L, 1431840029L, 318429286L, 3107687873L], [23, 529, 12167, 279841, 6436343, 148035889, 3404825447, 355856901, 389195885, 1155992517, 3201289377, 3470040129, 1855794587, 3705711311, 3378475354, 3647561181, 2041022364, 170437344, 22302493, 512957339, 104749540, 2409239420, 843916794L, 3819060586, 2087752260, 1245224952, 1355878963L, 3164797L, 72790331, 1674177613L, 3426277328L, 849250164L, 43971677L, 1011348571L, 3772235038L, 1010764656L, 3758804993L, 701873621L, 552067607L, 1004285704L, 3609789097L, 1172264432L, 3575543422L, 384613907L, 1050607023L, 777423015L, 2289703669L, 1992350940L, 2948751011L, 1559414130L], [24, 576, 13824, 331776, 7962624, 191102976, 688715005, 938134444, 3026444561, 2475053922, 934947843, 2949966137, 639571746, 3656452647, 2004222310, 1328258412, 696150536, 1116587188, 3411553998, 24411153, 585867672, 2367554871, 2252727038, 3394615465, 3515642780, 2522541921, 2074659819, 3018758628, 2290591530, 405606854, 1939051658, 3661919183, 2135419174, 579226729, 2208172239, 2325300289, 1238617070, 2442514747, 154007643, 3696183432, 2957761150L, 826652058, 350867297, 625302290L, 3313985703, 1580528492L, 2852876037, 2207165765, 2301144913, 658888046], [25, 625, 15625, 390625, 9765625, 244140625, 2205759206, 575390284, 2691487843, 1025336952, 2246885286, 1603542284, 1110992910, 490527817, 569926168, 2554884943, 1508020871, 2620714004, 3153747396, 888556520, 2725130905, 1866413502, 3785016941, 1079269469, 3595198211, 231557638, 1891184531, 506536247, 970136918, 866884436, 2183328805, 14630259, 365756475, 1348399037, 2527924573, 834011621, 1361508430, 2855659398, 1231869408, 3512440267, 2060365457, 838302978, 1468792355, 1640001104, 2022463410, 3788508222, 1166551494, 1879492417, 214233397, 1458078506], [26, 676, 17576, 456976, 11881376, 308915776, 236297338, 2245974369, 3826743728, 2051426453, 2666254331, 3060753483, 1624462178, 3258452438, 2866878589, 481471353, 824985921, 1960851851, 311314679, 298668816, 3867632797, 3114542247, 3022970042, 642092712, 1103384836, 1403710803, 1416673107, 1753693011, 2720697677, 578524060, 3348356303, 1306622660, 2790137808, 2383967466, 3516807831, 1788605969, 3628434585, 793145154, 1132991909, 2173494701, 1942272360, 3726004332, 3329958576, 828281758, 2046543613, 2539300491, 3657710062, 1554307556, 1434432266, 2215431145], [27, 729, 19683, 531441, 14348907, 387420489, 2664840365, 1791074313, 1585929423, 3842530231, 2406649343, 2615429557, 456982497, 645258162, 1830944698, 2662429818, 1725989544, 3726397079, 3168810658, 3705002967, 2591169634, 3699720995, 2448556390, 3746919826, 3722924827, 3075059854L, 1173731259, 508692641, 2041432050, 550075484, 3158768811, 3433873098, 3066176009, 933867444, 1827882474, 2579749770, 3391384667, 1918988372, 1141852597, 3545725186, 2188425966, 621154797L, 1180153843, 682102409, 2825739367, 2237590948, 1948609311, 1941617950, 1752851203, 553905453L], [28, 784, 21952, 614656, 17210368, 481890304, 1799659255, 3617382112, 3842788661, 2358659195, 3678354756, 1652266274, 3388135063, 1321627708, 1925768053, 3250672037L, 1370419399L, 3291935401L, 2525793591L, 562605006L, 161914492L, 635849357L, 2212756320L, 3490830675L, 299348425L, 586243062L, 823780060L, 3577059585L, 2713757905L, 1927849379L, 3308949165L, 3002178983L, 2208126725L, 3361202015L, 567502364L, 299040516L, 577621610L, 582379404L, 715597636L, 547951713L, 3649378707L, 840936902L, 159694742L, 573696357L, 472472320L, 1535955703L, 131439075L, 3680294100L, 1706567906L, 1010824340L], [29, 841, 24389, 707281, 20511149, 594823321, 1658850633, 1333591329, 3594340770, 2894215436, 2079362845, 1835176220, 2549276933, 3769415515, 175870203, 1202479468, 3689853220, 1766320067, 552448496, 429980708, 776171275, 3020184880, 1834720302, 2536055311, 3385988477, 749755358, 2254123287, 3005472619, 1408064733, 1856313067, 3162245496, 2056721747, 1178584378, 2996895610, 1159331472, 2438561336, 558663202, 610207182, 2104982602, 2578149173, 708954056, 1070885529, 3771385408, 232997100, 2859159481, 1062740150, 3535169417, 1178246199, 2987088419, 874922933], [30, 900, 27000, 810000, 24300000, 729000000, 2381217905, 1276921608, 3227840469, 3289060014, 1227889945, 1756890579, 2035883923, 2610171405, 350013770, 2704900262, 3191879480, 2210230344, 45051197, 1351535910, 1568513110, 282316272, 673975322, 730477565, 2425544855, 2606730108, 246774860, 3505489381, 3823014536, 1655499929, 2891920842, 1006984042, 2925226327, 2006148592, 1718111475, 872510803, 2788785576, 1810682481, 3649640983, 352049758, 2765979902, 1126512261, 2613316478, 444365960, 1637709543, 2358209262, 586662318, 2008843864, 1798969635, 3298255603], [31, 961, 29791, 923521, 28629151, 887503681, 228319178, 3180138099, 1140370594, 271680643, 626587095, 3833174269, 1895709769, 300656554, 1524840336, 496973388L, 3712905771L, 2065142750L, 1655322546L, 644165479L, 480347754L, 3197511117L, 1678934152L, 1376125265L, 3682319025L, 1116953624L, 3443510992L, 1509417439L, 18863581L, 584771011L, 2536875665L, 688017235L, 1839752190L, 2463728024L, 2318196783L, 1704484731L, 2168193214L, 952130511L, 2231750908L, 2922419025L, 946592138L, 2060061345L, 1497798991L, 3556448112L, 1112711740L, 3312012588L, 1330723334L, 2274859164L, 361018542L, 3396061964L], [32, 1024, 32768, 1048576, 33554432, 1073741824, 3177687016, 344317618, 3222650938, 1783163122, 2492630038, 1809032836, 3320460886, 1015325039, 1308349896, 2889632482, 2819841787, 586539547, 3178239828, 362007602, 3788730426, 408924643, 1392319319, 1678897599, 3053889721L, 280560597, 1182426266, 2757832741, 2500006494L, 2045079428, 3078438992, 1066137269, 2934341256, 352766136, 3493003514, 2638932716, 2592962113, 1121902817, 821082373, 2888097422, 2770719867, 2912394526, 3548227195, 508334089, 675665172, 2132503409, 1978249965, 939896176, 2792382699, 3605605150], [33, 1089, 35937, 1185921, 39135393, 1291467969, 3640878787, 3216307401, 898720920, 2373495427, 370220711, 524014206, 1701443122, 1579033160, 1437260833L, 656530461L, 2176723118L, 1672247352L, 615572750L, 825118655L, 3842377101L, 2070238925L, 2056025402L, 1586979143L, 1699478272L, 1514193110L, 3195295602L, 205331553L, 2878184830L, 1433945334L, 547118994L, 2463901126L, 3353608778L, 1531909942L, 3779951058L, 10179506L, 335923698L, 3289969196L, 3329560155L, 738305383L, 977539125L, 1076739773L, 452604738L, 3242687097L, 1769250888L, 3816689438L, 1222546046L, 1366455328L, 2217705215L, 3024656553L], [34, 1156, 39304, 1336336, 45435424, 1544804416, 1852516697, 621464994, 1641027701, 1226351968, 2718402722, 2777294911, 881872918, 2699384279, 2130667849, 2283091324, 3567733055, 472474881, 473120278, 495063776, 1241142708, 3221287882, 386608256, 1451411447, 2574912170, 1796372562, 2610320823, 3000266764, 667403082, 3202922693, 3659948249, 3607791477, 1834461229, 7579082, 257688788, 965905954, 1658751084, 1828946990, 3717851375, 1678741342, 2508615762, 3440051109, 29045136L, 987534624L, 2394125864, 3445150996L, 202441294, 2985247577, 156750724L, 1431768197], [35, 1225, 42875, 1500625, 52521875, 1838265625, 1975194171, 2869936862, 3003879695, 3794122431, 270566839, 1674326527, 135082160, 830119181, 1769876402, 3479327785, 946023486, 1928770658, 1245113907, 703666136, 1241776246, 586848001, 1050897940, 1701620129L, 1090358230L, 3082730279L, 2656136452, 3316378183, 3038300254, 1101085577, 3458187424, 206110851L, 3316123366L, 3029381659L, 788934752L, 328421387L, 3699235707L, 847287918L, 2370782197L, 1124492096L, 379659170L, 1594801693L, 1249469389L, 856108006L, 2679485277L, 235830639L, 458559527L, 458557769L, 458496239L, 456342689L], [36, 1296, 46656, 1679616, 60466176, 2176782336, 409035716, 3032016519, 15414952, 554938272, 488995697, 2012819416, 2301883434, 1014918825, 1457269929, 1790883997, 2107721188, 1820590807, 3177166348, 1343052377, 1576808544, 2196517718, 1119509468, 1324776658, 918882660, 1897724408, 2056219565, 3864288798, 2692922063, 3399040212, 1534998643, 691361282, 1502467638, 3418001521, 2217605767, 1878679232, 1370593229, 2568279216, 2809654139, 3703638529, 807268798, 1777381795, 1621641916, 3810519110, 757213295, 3873140106, 3011569151, 3177066123, 1339444277, 1446916944], [37, 1369, 50653, 1874161, 69343957, 2565726409, 1385723077, 600920402, 2745272779, 233425929, 841246535, 3841826862, 1828362810, 1387564847, 669065892, 1368899490, 3876204102, 3100320690, 1676929379, 3580040738, 3835545479, 1595951639, 583864358, 2114199151, 270240207, 2203374821, 3569739997, 3454418062, 3085262886, 1119790631, 2454689157, 1175101172, 603422755, 2837859840, 3659147186, 2864727636, 755499219, 669176170, 1372979776, 129418265, 890719386, 1774565930, 3294836706, 1078509133, 927273731, 3127076695, 2666901564, 1231447393, 2688232932, 2020708009], [38, 1444, 54872, 2085136, 79235168, 3010936384, 1380646441, 1793731311, 1899930695, 2037750868, 3377161023, 3603913466, 527237043, 546225539, 1267788387, 1402881678, 2638670317, 2825561571, 2131916385, 3057694250, 3157445349, 3050230692, 2873830145, 68365778, 2597899564, 1276272957, 1725295338, 3197120140, 660116331, 1697882064, 2155415728, 52912865, 2010688870, 2348805099, 3503952544, 626478426, 419641674, 355357936, 1810332311, 2530768695, 2623056354, 2232230977, 2971892327, 3794728694, 3880459288, 3240465441, 2307237769, 1924394004, 2967356610, 3622371448], [39, 1521, 59319, 2313441, 90224199, 3518743761, 809532014, 389697194, 3504921309, 270456386, 2752286216, 2099739111, 36940530, 1440680670, 1617956264, 736191592, 1427177155, 1091319179, 3583883791, 3349993184, 2023772349, 971993231, 2827928238, 1152021550, 2053519841, 2132145419, 1300786542, 59841691, 2333825949, 1370814374, 2790927139, 3606735108, 343438128, 1700817735, 70032542, 2731269138, 1280073069, 3149772663L, 2010684868, 461581472, 2410651732L, 469263492, 2710250512L, 460346655, 2362493869, 2488863254, 3519512850, 839526485, 1559481563, 2353434672], [40, 1600, 64000, 2560000, 102400000, 198243581, 134230402, 1471459661, 392040155, 90580524, 3623220960, 711850897, 1189740947, 816560852, 1480382728, 748962835, 2674218467, 1729315367, 2910755557, 3395286129, 3287726914, 2883114733, 2289653169, 1937729123, 3451792959, 1650243695, 3645645096, 1608816337, 1988550776, 1586902660, 1112003696, 1604827231, 1828986536, 2999845898, 3061143350, 1615285011, 2247297736, 243511803, 1944959282, 3740999319, 1525228838, 2542807235, 370622506, 3131630983, 537033912, 1992574385, 1747847020, 3652021677, 1863879577, 497811119], [41, 1681, 68921, 2825761, 115856201, 852347822, 3764209350, 2320083009, 1577249313, 2303119129, 881730233, 1071131782, 1041082453, 3706816383, 3864727781, 2543582261, 2945205807, 3820745517, 740309437, 3068391984, 1075865936, 1235182767, 3869416419L, 2735816419, 3031293447, 3452582338, 1236644774, 31602287, 1295693767, 2452611000L, 3113140525L, 2910556117, 2400108227, 960526832, 404035922, 974447126, 974767976, 987922826, 1527271676L, 254036012, 2619963654, 2179086501, 3591905323, 3051130740, 368154932, 3401082955L, 3022926490L, 3109537101, 2762815733, 240508902L], [42, 1764, 74088, 3111696, 130691232, 1591275325, 571704527, 625051620, 2865629526, 3423747522, 3478164840, 1865935777, 414174254, 1804292992, 1722933703, 2203599984, 2902801691, 1087222033, 2788004777, 163508064, 2969582269, 3892006309, 3656251799, 1550075217, 2739056410, 2005433069, 2375304099, 2318861683, 3846036630, 1725525281, 2312446260, 3576588864, 2101988366, 2532870154, 1141123155, 1154095482, 1698933216, 1195579530, 3441263232, 316068241, 1581596865L, 165209207L, 3041030275L, 2995066142, 1064572556, 1836726743, 3085151245, 950390463, 938835256L, 453516562], [43, 1849, 79507, 3418801, 147008443, 2423606630, 2873418196, 2726533439, 308245307, 1561278944, 873135469, 2465017396, 756324715, 1339911393, 3047600033, 2420839592, 2754435562, 1508036596, 2481470924, 1463826419, 580433313, 1572093945, 1338180512, 2973172150, 3118197042, 1558754560, 764586957, 1695187799, 2733459815, 606079475, 2674878911, 1984857022, 3495967147, 2211843399, 1563112101, 951961220, 1956768270, 2288150811, 946574398, 1725134924, 123429771, 1409723734, 2151774277, 2877896274, 2919090793, 792698691, 2903992361, 143466115, 2271286526, 221410143], [44, 1936, 85184, 3748096, 164916224, 3358557437, 3559539725, 709491140, 35558808, 1564587552, 2579993165, 484763109, 1840794701, 3039838464, 1229174170, 3412830033, 2049777530, 541813683, 453263538, 454813577, 523015293, 3523890797L, 3038694727L, 1178849742, 1198555201, 2065595397, 1237799831, 3792359117, 3158031550, 2531913535L, 2267015808, 2304785077L, 68876494L, 3030565736L, 821174138L, 1051854301L, 3406268635L, 1761076018L, 3429972831L, 2804060642L, 2548219259L, 2984467664L, 2690615389L, 1454384546L, 1628817320L, 1508346538L, 105388549L, 739339737L, 1348897076L, 885125059L], [45, 2025, 91125, 4100625, 184528125, 508252787, 3382593320, 204199059, 1393444817, 340914061, 3647863488, 448087362, 675149195, 3097418842, 2962373225, 783076879, 158651784, 3241573861, 1653836242, 365258929, 845626129, 2973368034, 1277843284, 2934357914, 3420144303, 1893993294, 3376813431, 3841860473, 1382438849, 3743401920, 849560383, 3150409464, 1449194796, 2849663116, 3506634812, 1888309780, 3121055301, 128257461, 1873829326L, 2469434871, 1987389463, 3681884617, 1979038167L, 3306076297, 658689443, 2356730002L, 813426777L, 1524397194, 2336014607, 3778990421L], [46, 2116, 97336, 4477456, 205962976, 1678784058, 3166694707, 1450969019, 482715751, 2716142451, 214347338, 2064464710, 1419222604, 2920137080, 1802587434, 1066137165, 2269232562, 3043030958, 3557949403, 3857659359, 2053291659, 905262258, 2664499678, 1736536199, 1925536774, 2824050386, 1280355929, 430026449, 292434559, 1758720457, 2946012642, 2992863286, 1250236491, 2942288720, 2821562874, 1165930377, 2961963895, 3726620924, 3821036487L, 368639547, 1366393486, 489997652, 3051109897, 31824178, 1463912188, 1078101525, 2819593122, 1075321785, 2691725082, 2988904783], [47, 2209, 103823, 4879681, 229345007, 2983702491, 3812542412, 3790454509, 2752323068, 733222369, 3279399991, 2119299236, 2163153617, 326553105L, 3654726678L, 270871430L, 1037687953L, 1998256763L, 371913805L, 1888923159L, 3028747255L, 2031889901L, 1952671291L, 2127153040L, 2532282405L, 2084580465L, 531371380L, 1587916346L, 574696301L, 3624187633L, 2733292734L, 3736553090L, 218956375L, 2495436787L, 352836419L, 992286017L, 3762122190L, 1420704075L, 511232402L, 641384380L, 2860770927L, 1932515323L, 1179822544L, 883069702L, 2526711804L, 1822762218L, 3816939447L, 99358735L, 772104126L, 1209086151L], [48, 2304, 110592, 5308416, 254803968, 537321207, 2404879422, 2399276105, 2130316889, 913543778, 974780735, 16398252, 787116096, 2701764837, 1058750349, 149183305, 3263042221, 715769848, 3174901352, 382764555, 2781672964, 996584026, 1062956220, 351065113, 1260099748, 2018441619, 3339043656, 466082309, 2883168737, 1970624711, 1043832072, 3330862428, 73383365, 3522401520, 1471746943, 484237722, 3754628561, 925375654, 1542710783, 3890502042, 3549546323, 2774697487, 661761130, 582482888, 674883691, 1212365816, 3624969302, 2497244060, 2935022310L, 561839796], [49, 2401, 117649, 5764801, 282475249, 2148017944, 13455943, 659341207, 1125667791, 589131893, 1583167824, 3517851415, 873436899, 3820843861, 129041077, 2425256354, 1904868776, 3690172387, 1521651689, 503560800, 1287940686, 744990910, 1424746819, 3550735008, 2484732956, 921465855, 2276506286, 2411628282, 1237093248, 2151222867L, 170497170, 558848492, 99281175, 967021156, 610959616, 2652726251, 1357624472, 261740005, 1131990988, 898968546, 1174138145, 2964179239, 1027795208, 3588888164, 456481181, 2878795774, 741761842, 1266522487, 3593255578, 670484467], [50, 2500, 125000, 6250000, 312500000, 33974324, 1698716200, 3082925201, 2133759709, 1448562137, 2268491308, 389629249, 3890436774, 3531774169, 1189669595, 1017133465L, 185839803L, 1496477312L, 766493639L, 3244874179L, 2435695771L, 954339561L, 943901022L, 421974072L, 1609921505L, 2540946870L, 2319138092L, 2921968449L, 1881434947L, 525593294L, 2893126186L, 439321797L, 2477307755L, 3034938761L, 3632194128L, 2312911126L, 2610620149L, 1905045623L, 1706127094L, 3453469901L, 1172212614L, 144284415L, 3316464331L, 2117446952L, 632924287L, 464162998L, 3719367805L, 2773838557L, 2270453185L, 487723099L]] bb = [3458, 769825472, 3204744481, 50527469, 2357423510, 797187995, 1630526331, 666397992, 187102374, 2849793570, 2741054782, 273042423, 707747831, 2225649389, 691941190, 3151998850, 1621081395, 3438064481, 263006000, 3192825386, 2637813968, 3091893577, 2390676034, 902134442, 998718565, 742841046, 2437712480, 3207683717, 1635135657, 2756484909, 3670558726, 3755834847, 3437555016, 2802207988, 315943137, 2729342941, 2230907266, 1103884307, 1226743026, 3719286678, 2952139380, 2320366504, 325451083, 2633706365, 2800841088, 3689011934, 699339465, 3489111800, 1658437944, 267980761] n = 50 R = IntegerModRing(3897756419) A = Matrix(R, [i[:n] for i in AA[:n]]) b = vector(R, [i - 125 for i in bb[:n]]) s = A.solve_right(b) if all([i < 128 for i in s]): print s
(115, 97, 109, 116, 115, 105, 114, 104, 67, 95, 121, 114, 114, 51, 109, 95, 52, 95, 117, 111, 121, 95, 104, 115, 49, 119, 95, 51, 87, 123, 83, 65, 77, 45, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)