{1, 1}
{2, 4}
{3, -9}
{4, 16}
{5, -66}
{6, -36}
{7, 176}
{8, 64}
{9, 81}
{10, -264}
{11, -60}
{12, -144}
{13, -658}
{14, 704}
{15, 594}
{16, 256}
{17, -414}
{18, 324}
{19, 956}
{20, -1056}
{21, -1584}
{22, -240}
{23, 600}
{24, -576}
{25, 1231}
{26, -2632}
{27, -729}
{28, 2816}
{29, 5574}
{30, 2376}
{31, -3592}
{32, 1024}
{33, 540}
{34, -1656}
{35, -11616}
{36, 1296}
{37, -8458}
{38, 3824}
{39, 5922}
{40, -4224}
{41, 19194}
{42, -6336}
{43, 13316}
{44, -960}
{45, -5346}
{46, 2400}
{47, -19680}
{48, -2304}
{49, 14169}
{50, 4924}
{51, 3726}
{52, -10528}
{53, -31266}
{54, -2916}
{55, 3960}
{56, 11264}
{57, -8604}
{58, 22296}
{59, 26340}
{60, 9504}
{61, -31090}
{62, -14368}
{63, 14256}
{64, 4096}
{65, 43428}
{66, 2160}
{67, -16804}
{68, -6624}
{69, -5400}
{70, -46464}
{71, 6120}
{72, 5184}
{73, -25558}
{74, -33832}
{75, -11079}
{76, 15296}
{77, -10560}
{78, 23688}
{79, 74408}
{80, -16896}
{81, 6561}
{82, 76776}
{83, -6468}
{84, -25344}
{85, 27324}
{86, 53264}
{87, -50166}
{88, -3840}
{89, -32742}
{90, -21384}
{91, -115808}
{92, 9600}
{93, 32328}
{94, -78720}
{95, -63096}
{96, -9216}
{97, 166082}
{98, 56676}
{99, -4860}
{100, 19696}
{101, -22002}
{102, 14904}
{103, -79264}
{104, -42112}
{105, 104544}
{106, -125064}
{107, 227988}
{108, -11664}
{109, -8530}
{110, 15840}
{111, 76122}
{112, 45056}
{113, -195438}
{114, -34416}
{115, -39600}
{116, 89184}
{117, -53298}
{118, 105360}
{119, -72864}
{120, 38016}
{121, -157451}
{122, -124360}
{123, -172746}
{124, -57472}
{125, 125004}
{126, 57024}
{127, 173000}
{128, 16384}
{129, -119844}
{130, 173712}
{131, 151260}
{132, 8640}
{133, 168256}
{134, -67216}
{135, 48114}
{136, -26496}
{137, -128454}
{138, -21600}
{139, 154196}
{140, -185856}
{141, 177120}
{142, 24480}
{143, 39480}
{144, 20736}
{145, -367884}
{146, -102232}
{147, -127521}
{148, -135328}
{149, 29454}
{150, -44316}
{151, -203872}
{152, 61184}
{153, -33534}
{154, -42240}
{155, 237072}
{156, 94752}
{157, 136142}
{158, 297632}
{159, 281394}
{160, -67584}
{161, 105600}
{162, 26244}
{163, -171124}
{164, 307104}
{165, -35640}
{166, -25872}
{167, -676200}
{168, -101376}
{169, 61671}
{170, 109296}
{171, 77436}
{172, 213056}
{173, 133158}
{174, -200664}
{175, 216656}
{176, -15360}
{177, -237060}
{178, -130968}
{179, -693396}
{180, -85536}
{181, 377174}
{182, -463232}
{183, 279810}
{184, 38400}
{185, 558228}
{186, 129312}
{187, 24840}
{188, -314880}
{189, -128304}
{190, -252384}
{191, -265344}
{192, -36864}
{193, 295298}
{194, 664328}
{195, -390852}
{196, 226704}
{197, 201294}
{198, -19440}
{199, 652448}
{200, 78784}
{201, 151236}
{202, -88008}
{203, 981024}
{204, 59616}
{205, -1266804}
{206, -317056}
{207, 48600}
{208, -168448}
{209, -57360}
{210, 418176}
{211, -1147060}
{212, -500256}
{213, -55080}
{214, 911952}
{215, -878856}
{216, -46656}
{217, -632192}
{218, -34120}
{219, 230022}
{220, 63360}
{221, 272412}
{222, 304488}
{223, 701960}
{224, 180224}
{225, 99711}
{226, -781752}
{227, 1236108}
{228, -137664}
{229, 105830}
{230, -158400}
{231, 95040}
{232, 356736}
{233, -438678}
{234, -213192}
{235, 1298880}
{236, 421440}
{237, -669672}
{238, -291456}
{239, 28464}
{240, 152064}
{241, 892562}
{242, -629804}
{243, -59049}
{244, -497440}
{245, -935154}
{246, -690984}
{247, -629048}
{248, -229888}
{249, 58212}
{250, 500016}
{251, -110124}
{252, 228096}
{253, -36000}
{254, 692000}
{255, -245916}
{256, 65536}
{257, 140802}
{258, -479376}
{259, -1488608}
{260, 694848}
{261, 451494}
{262, 605040}
{263, -938760}
{264, 34560}
{265, 2063556}
{266, 673024}
{267, 294678}
{268, -268864}
{269, -1114506}
{270, 192456}
{271, 567704}
{272, -105984}
{273, 1042272}
{274, -513816}
{275, -73860}
{276, -86400}
{277, -1213258}
{278, 616784}
{279, -290952}
{280, -743424}
{281, 687738}
{282, 708480}
{283, -830908}
{284, 97920}
{285, 567864}
{286, 157920}
{287, 3378144}
{288, 82944}
{289, -1248461}
{290, -1471536}
{291, -1494738}
{292, -408928}
{293, -1312626}
{294, -510084}
{295, -1738440}
{296, -541312}
{297, 43740}
{298, 117816}
{299, -394800}
{300, -177264}
{301, 2343616}
{302, -815488}
{303, 198018}
{304, 244736}
{305, 2051940}
{306, -134136}
{307, 1690220}
{308, -168960}
{309, 713376}
{310, 948288}
{311, -1502040}
{312, 379008}
{313, 810842}
{314, 544568}
{315, -940896}
{316, 1190528}
{317, 903558}
{318, 1125576}
{319, -334440}
{320, -270336}
{321, -2051892}
{322, 422400}
{323, -395784}
{324, 104976}
{325, -809998}
{326, -684496}
{327, 76770}
{328, 1228416}
{329, -3463680}
{330, -142560}
{331, 1121972}
{332, -103488}
{333, -685098}
{334, -2704800}
{335, 1109064}
{336, -405504}
{337, -2752174}
{338, 246684}
{339, 1758942}
{340, 437184}
{341, 215520}
{342, 309744}
{343, -464288}
{344, 852224}
{345, 356400}
{346, 532632}
{347, 1917492}
{348, -802656}
{349, 1836590}
{350, 866624}
{351, 479682}
{352, -61440}
{353, -622014}
{354, -948240}
{355, -403920}
{356, -523872}
{357, 655776}
{358, -2773584}
{359, 3740616}
{360, -342144}
{361, -1562163}
{362, 1508696}
{363, 1417059}
{364, -1852928}
{365, 1686828}
{366, 1119240}
{367, 16232}
{368, 153600}
{369, 1554714}
{370, 2232912}
{371, -5502816}
{372, 517248}
{373, 293606}
{374, 99360}
{375, -1125036}
{376, -1259520}
{377, -3667692}
{378, -513216}
{379, 3180116}
{380, -1009536}
{381, -1557000}
{382, -1061376}
{383, -2979840}
{384, -147456}
{385, 696960}
{386, 1181192}
{387, 1078596}
{388, 2657312}
{389, 3459774}
{390, -1563408}
{391, -248400}
{392, 906816}
{393, -1361340}
{394, 805176}
{395, -4910928}
{396, -77760}
{397, -3904162}
{398, 2609792}
{399, -1514304}
{400, 315136}
{401, 5441154}
{402, 604944}
{403, 2363536}
{404, -352032}
{405, -433026}
{406, 3924096}
{407, 507480}
{408, 238464}
{409, 1969946}
{410, -5067216}
{411, 1156086}
{412, -1268224}
{413, 4635840}
{414, 194400}
{415, 426888}
{416, -673792}
{417, -1387764}
{418, -229440}
{419, 139020}
{420, 1672704}
{421, 4327430}
{422, -4588240}
{423, -1594080}
{424, -2001024}
{425, -509634}
{426, -220320}
{427, -5471840}
{428, 3647808}
{429, -355320}
{430, -3515424}
{431, -2799360}
{432, -186624}
{433, -5902414}
{434, -2528768}
{435, 3310956}
{436, -136480}
{437, 573600}
{438, 920088}
{439, -446512}
{440, 253440}
{441, 1147689}
{442, 1089648}
{443, 3495252}
{444, 1217952}
{445, 2160972}
{446, 2807840}
{447, -265086}
{448, 720896}
{449, -1206126}
{450, 398844}
{451, -1151640}
{452, -3127008}
{453, 1834848}
{454, 4944432}
{455, 7643328}
{456, -550656}
{457, 233546}
{458, 423320}
{459, 301806}
{460, -633600}
{461, -1744890}
{462, 380160}
{463, -2917864}
{464, 1426944}
{465, -2133648}
{466, -1754712}
{467, -5310756}
{468, -852768}
{469, -2957504}
{470, 5195520}
{471, -1225278}
{472, 1685760}
{473, -798960}
{474, -2678688}
{475, 1176836}
{476, -1165824}
{477, -2532546}
{478, 113856}
{479, 2344656}
{480, 608256}
{481, 5565364}
{482, 3570248}
{483, -950400}
{484, -2519216}
{485, -10961412}
{486, -236196}
{487, 9815312}
{488, -1989760}
{489, 1540116}
{490, -3740616}
{491, -5945196}
{492, -2763936}
{493, -2307636}
{494, -2516192}
{495, 320760}
{496, -919552}
{497, 1077120}
{498, 232848}
{499, 6478316}
{500, 2000064}
{501, 6085800}
{502, -440496}
{503, 4717944}
{504, 912384}
{505, 1452132}
{506, -144000}
{507, -555039}
{508, 2768000}
{509, -1907706}
{510, -983664}
{511, -4498208}
{512, 262144}
{513, -696924}
{514, 563208}
{515, 5231424}
{516, -1917504}
{517, 1180800}
{518, -5954432}
{519, -1198422}
{520, 2779392}
{521, 8019738}
{522, 1805976}
{523, 1911620}
{524, 2420160}
{525, -1949904}
{526, -3755040}
{527, 1487088}
{528, 138240}
{529, -6076343}
{530, 8254224}
{531, 2133540}
{532, 2692096}
{533, -12629652}
{534, 1178712}
{535, -15047208}
{536, -1075456}
{537, 6240564}
{538, -4458024}
{539, -850140}
{540, 769824}
{541, -11990050}
{542, 2270816}
{543, -3394566}
{544, -423936}
{545, 562980}
{546, 4169088}
{547, 4458092}
{548, -2055264}
{549, -2518290}
{550, -295440}
{551, 5328744}
{552, -345600}
{553, 13095808}
{554, -4853032}
{555, -5024052}
{556, 2467136}
{557, 9026118}
{558, -1163808}
{559, -8761928}
{560, -2973696}
{561, -223560}
{562, 2750952}
{563, 6848988}
{564, 2833920}
{565, 12898908}
{566, -3323632}
{567, 1154736}
{568, 391680}
{569, -5463222}
{570, 2271456}
{571, -10232380}
{572, 631680}
{573, 2388096}
{574, 13512576}
{575, 738600}
{576, 331776}
{577, 15943682}
{578, -4993844}
{579, -2657682}
{580, -5886144}
{581, -1138368}
{582, -5978952}
{583, 1875960}
{584, -1635712}
{585, 3517668}
{586, -5250504}
{587, -9477132}
{588, -2040336}
{589, -3433952}
{590, -6953760}
{591, -1811646}
{592, -2165248}
{593, 2453490}
{594, 174960}
{595, 4809024}
{596, 471264}
{597, -5872032}
{598, -1579200}
{599, -9299784}
{600, -709056}
{601, -11461702}
{602, 9374464}
{603, -1361124}
{604, -3261952}
{605, 10391766}
{606, 792072}
{607, 11278376}
{608, 978944}
{609, -8829216}
{610, 8207760}
{611, 12949440}
{612, -536544}
{613, 93782}
{614, 6760880}
{615, 11401236}
{616, -675840}
{617, -14964150}
{618, 2853504}
{619, -5068876}
{620, 3793152}
{621, -437400}
{622, -6008160}
{623, -5762592}
{624, 1516032}
{625, -12097139}
{626, 3243368}
{627, 516240}
{628, 2178272}
{629, 3501612}
{630, -3763584}
{631, 15591872}
{632, 4762112}
{633, 10323540}
{634, 3614232}
{635, -11418000}
{636, 4502304}
{637, -9323202}
{638, -1337760}
{639, 495720}
{640, -1081344}
{641, 10970130}
{642, -8207568}
{643, -2837044}
{644, 1689600}
{645, 7909704}
{646, -1583136}
{647, -6056856}
{648, 419904}
{649, -1580400}
{650, -3239992}
{651, 5689728}
{652, -2737984}
{653, -1088922}
{654, 307080}
{655, -9983160}
{656, 4913664}
{657, -2070198}
{658, -13854720}
{659, 7418028}
{660, -570240}
{661, 767654}
{662, 4487888}
{663, -2451708}
{664, -413952}
{665, -11104896}
{666, -2740392}
{667, 3344400}
{668, -10819200}
{669, -6317640}
{670, 4436256}
{671, 1865400}
{672, -1622016}
{673, 1422626}
{674, -11008696}
{675, -897399}
{676, 986736}
{677, -6162306}
{678, 7035768}
{679, 29230432}
{680, 1748736}
{681, -11124972}
{682, 862080}
{683, 15062148}
{684, 1238976}
{685, 8477964}
{686, -1857152}
{687, -952470}
{688, 3408896}
{689, 20573028}
{690, 1425600}
{691, -5876356}
{692, 2130528}
{693, -855360}
{694, 7669968}
{695, -10176936}
{696, -3210624}
{697, -7946316}
{698, 7346360}
{699, 3948102}
{700, 3466496}
{701, 3600774}
{702, 1918728}
{703, -8085848}
{704, -245760}
{705, -11689920}
{706, -2488056}
{707, -3872352}
{708, -3792960}
{709, 9225158}
{710, -1615680}
{711, 6027048}
{712, -2095488}
{713, -2155200}
{714, 2623104}
{715, -2605680}
{716, -11094336}
{717, -256176}
{718, 14962464}
{719, -26392320}
{720, -1368576}
{721, -13950464}
{722, -6248652}
{723, -8033058}
{724, 6034784}
{725, 6861594}
{726, 5668236}
{727, -9794848}
{728, -7411712}
{729, 531441}
{730, 6747312}
{731, -5512824}
{732, 4476960}
{733, 4075838}
{734, 64928}
{735, 8416386}
{736, 614400}
{737, 1008240}
{738, 6218856}
{739, -16570852}
{740, 8931648}
{741, 5661432}
{742, -22011264}
{743, 14414136}
{744, 2068992}
{745, -1943964}
{746, 1174424}
{747, -523908}
{748, 397440}
{749, 40125888}
{750, -4500144}
{751, 16794440}
{752, -5038080}
{753, 991116}
{754, -14670768}
{755, 13455552}
{756, -2052864}
{757, 13294262}
{758, 12720464}
{759, 324000}
{760, -4038144}
{761, -2147862}
{762, -6228000}
{763, -1501280}
{764, -4245504}
{765, 2213244}
{766, -11919360}
{767, -17331720}
{768, -589824}
{769, -13105918}
{770, 2787840}
{771, -1267218}
{772, 4724768}
{773, -23715378}
{774, 4314384}
{775, -4421752}
{776, 10629248}
{777, 13397472}
{778, 13839096}
{779, 18349464}
{780, -6253632}
{781, -367200}
{782, -993600}
{783, -4063446}
{784, 3627264}
{785, -8985372}
{786, -5445360}
{787, -8400484}
{788, 3220704}
{789, 8448840}
{790, -19643712}
{791, -34397088}
{792, -311040}
{793, 20457220}
{794, -15616648}
{795, -18572004}
{796, 10439168}
{797, 5410230}
{798, -6057216}
{799, 8147520}
{800, 1260544}
{801, -2652102}
{802, 21764616}
{803, 1533480}
{804, 2419776}
{805, -6969600}
{806, 9454144}
{807, 10030554}
{808, -1408128}
{809, -26077734}
{810, -1732104}
{811, 19002116}
{812, 15696384}
{813, -5109336}
{814, 2029920}
{815, 11294184}
{816, 953856}
{817, 12730096}
{818, 7879784}
{819, -9380448}
{820, -20268864}
{821, -31017282}
{822, 4624344}
{823, -15628960}
{824, -5072896}
{825, 664740}
{826, 18543360}
{827, 15842052}
{828, 777600}
{829, 2061758}
{830, 1707552}
{831, 10919322}
{832, -2695168}
{833, -5865966}
{834, -5551056}
{835, 44629200}
{836, -917760}
{837, 2618568}
{838, 556080}
{839, 30390024}
{840, 6690816}
{841, 10558327}
{842, 17309720}
{843, -6189642}
{844, -18352960}
{845, -4070286}
{846, -6376320}
{847, -27711376}
{848, -8004096}
{849, 7478172}
{850, -2038536}
{851, -5074800}
{852, -881280}
{853, -29773786}
{854, -21887360}
{855, -5110776}
{856, 14591232}
{857, 8641002}
{858, -1421280}
{859, -33566284}
{860, -14061696}
{861, -30403296}
{862, -11197440}
{863, 39019104}
{864, -746496}
{865, -8788428}
{866, -23609656}
{867, 11236149}
{868, -10115072}
{869, -4464480}
{870, 13243824}
{871, 11057032}
{872, -545920}
{873, 13452642}
{874, 2294400}
{875, 22000704}
{876, 3680352}
{877, -18138178}
{878, -1786048}
{879, 11813634}
{880, 1013760}
{881, 30531186}
{882, 4590756}
{883, -43553284}
{884, 4358592}
{885, 15645960}
{886, 13981008}
{887, -13415160}
{888, 4871808}
{889, 30448000}
{890, 8643888}
{891, -393660}
{892, 11231360}
{893, -18814080}
{894, -1060344}
{895, 45764136}
{896, 2883584}
{897, 3553200}
{898, -4824504}
{899, -20021808}
{900, 1595376}
{901, 12944124}
{902, -4606560}
{903, -21092544}
{904, -12508032}
{905, -24893484}
{906, 7339392}
{907, 3108164}
{908, 19777728}
{909, -1782162}
{910, 30573312}
{911, 1190352}
{912, -2202624}
{913, 388080}
{914, 934184}
{915, -18467460}
{916, 1693280}
{917, 26621760}
{918, 1207224}
{919, -47199616}
{920, -2534400}
{921, -15211980}
{922, -6979560}
{923, -4026960}
{924, 1520640}
{925, -10411798}
{926, -11671456}
{927, -6420384}
{928, 5707776}
{929, 1335954}
{930, -8534592}
{931, 13545564}
{932, -7018848}
{933, 13518360}
{934, -21243024}
{935, -1639440}
{936, -3411072}
{937, 14723786}
{938, -11830016}
{939, -7297578}
{940, 20782080}
{941, -26919642}
{942, -4901112}
{943, 11516400}
{944, 6743040}
{945, 8468064}
{946, -3195840}
{947, -3731604}
{948, -10714752}
{949, 16817164}
{950, 4707344}
{951, -8132022}
{952, -4663296}
{953, 21873546}
{954, -10130184}
{955, 17512704}
{956, 455424}
{957, 3009960}
{958, 9378624}
{959, -22607904}
{960, 2433024}
{961, -15726687}
{962, 22261456}
{963, 18467028}
{964, 14280992}
{965, -19489668}
{966, -3801600}
{967, 17602496}
{968, -10076864}
{969, 3562056}
{970, -43845648}
{971, 16731684}
{972, -944784}
{973, 27138496}
{974, 39261248}
{975, 7289982}
{976, -7959040}
{977, 55538178}
{978, 6160464}
{979, 1964520}
{980, -14962464}
{981, -690930}
{982, -23780784}
{983, -38678424}
{984, -11055744}
{985, -13285404}
{986, -9230544}
{987, 31173120}
{988, -10064768}
{989, 7989600}
{990, 1283040}
{991, 9584984}
{992, -3678208}
{993, -10097748}
{994, 4308480}
{995, -43061568}
{996, 931392}
{997, -10365034}
{998, 25913264}
{999, 6165882}
{1000, 8000256}