{1, 1}
{2, 0}
{3, -27}
{4, 64}
{5, 0}
{6, 0}
{7, -286}
{8, 0}
{9, 729}
{10, 0}
{11, 0}
{12, -1728}
{13, 506}
{14, 0}
{15, 0}
{16, 4096}
{17, 0}
{18, 0}
{19, -10582}
{20, 0}
{21, 7722}
{22, 0}
{23, 0}
{24, 0}
{25, 15625}
{26, 0}
{27, -19683}
{28, -18304}
{29, 0}
{30, 0}
{31, 35282}
{32, 0}
{33, 0}
{34, 0}
{35, 0}
{36, 46656}
{37, -89206}
{38, 0}
{39, -13662}
{40, 0}
{41, 0}
{42, 0}
{43, 111386}
{44, 0}
{45, 0}
{46, 0}
{47, 0}
{48, -110592}
{49, -35853}
{50, 0}
{51, 0}
{52, 32384}
{53, 0}
{54, 0}
{55, 0}
{56, 0}
{57, 285714}
{58, 0}
{59, 0}
{60, 0}
{61, -420838}
{62, 0}
{63, -208494}
{64, 262144}
{65, 0}
{66, 0}
{67, 172874}
{68, 0}
{69, 0}
{70, 0}
{71, 0}
{72, 0}
{73, 638066}
{74, 0}
{75, -421875}
{76, -677248}
{77, 0}
{78, 0}
{79, -204622}
{80, 0}
{81, 531441}
{82, 0}
{83, 0}
{84, 494208}
{85, 0}
{86, 0}
{87, 0}
{88, 0}
{89, 0}
{90, 0}
{91, -144716}
{92, 0}
{93, -952614}
{94, 0}
{95, 0}
{96, 0}
{97, -56446}
{98, 0}
{99, 0}
{100, 1000000}
{101, 0}
{102, 0}
{103, 1126946}
{104, 0}
{105, 0}
{106, 0}
{107, 0}
{108, -1259712}
{109, -2172742}
{110, 0}
{111, 2408562}
{112, -1171456}
{113, 0}
{114, 0}
{115, 0}
{116, 0}
{117, 368874}
{118, 0}
{119, 0}
{120, 0}
{121, 1771561}
{122, 0}
{123, 0}
{124, 2258048}
{125, 0}
{126, 0}
{127, -3952366}
{128, 0}
{129, -3007422}
{130, 0}
{131, 0}
{132, 0}
{133, 3026452}
{134, 0}
{135, 0}
{136, 0}
{137, 0}
{138, 0}
{139, 1264538}
{140, 0}
{141, 0}
{142, 0}
{143, 0}
{144, 2985984}
{145, 0}
{146, 0}
{147, 968031}
{148, -5709184}
{149, 0}
{150, 0}
{151, -3830398}
{152, 0}
{153, 0}
{154, 0}
{155, 0}
{156, -874368}
{157, 7082714}
{158, 0}
{159, 0}
{160, 0}
{161, 0}
{162, 0}
{163, 2898506}
{164, 0}
{165, 0}
{166, 0}
{167, 0}
{168, 0}
{169, -4570773}
{170, 0}
{171, -7714278}
{172, 7128704}
{173, 0}
{174, 0}
{175, -4468750}
{176, 0}
{177, 0}
{178, 0}
{179, 0}
{180, 0}
{181, 98282}
{182, 0}
{183, 11362626}
{184, 0}
{185, 0}
{186, 0}
{187, 0}
{188, 0}
{189, 5629338}
{190, 0}
{191, 0}
{192, -7077888}
{193, -13055614}
{194, 0}
{195, 0}
{196, -2294592}
{197, 0}
{198, 0}
{199, 11654498}
{200, 0}
{201, -4667598}
{202, 0}
{203, 0}
{204, 0}
{205, 0}
{206, 0}
{207, 0}
{208, 2072576}
{209, 0}
{210, 0}
{211, 17597162}
{212, 0}
{213, 0}
{214, 0}
{215, 0}
{216, 0}
{217, -10090652}
{218, 0}
{219, -17227782}
{220, 0}
{221, 0}
{222, 0}
{223, -11810734}
{224, 0}
{225, 11390625}
{226, 0}
{227, 0}
{228, 18285696}
{229, -4072822}
{230, 0}
{231, 0}
{232, 0}
{233, 0}
{234, 0}
{235, 0}
{236, 0}
{237, 5524794}
{238, 0}
{239, 0}
{240, 0}
{241, 26439842}
{242, 0}
{243, -14348907}
{244, -26933632}
{245, 0}
{246, 0}
{247, -5354492}
{248, 0}
{249, 0}
{250, 0}
{251, 0}
{252, -13343616}
{253, 0}
{254, 0}
{255, 0}
{256, 16777216}
{257, 0}
{258, 0}
{259, 25512916}
{260, 0}
{261, 0}
{262, 0}
{263, 0}
{264, 0}
{265, 0}
{266, 0}
{267, 0}
{268, 11063936}
{269, 0}
{270, 0}
{271, -39145678}
{272, 0}
{273, 3907332}
{274, 0}
{275, 0}
{276, 0}
{277, -26266966}
{278, 0}
{279, 25720578}
{280, 0}
{281, 0}
{282, 0}
{283, -13970374}
{284, 0}
{285, 0}
{286, 0}
{287, 0}
{288, 0}
{289, 24137569}
{290, 0}
{291, 1524042}
{292, 40836224}
{293, 0}
{294, 0}
{295, 0}
{296, 0}
{297, 0}
{298, 0}
{299, 0}
{300, -27000000}
{301, -31856396}
{302, 0}
{303, 0}
{304, -43343872}
{305, 0}
{306, 0}
{307, 55340714}
{308, 0}
{309, -30427542}
{310, 0}
{311, 0}
{312, 0}
{313, 38871506}
{314, 0}
{315, 0}
{316, -13095808}
{317, 0}
{318, 0}
{319, 0}
{320, 0}
{321, 0}
{322, 0}
{323, 0}
{324, 34012224}
{325, 7906250}
{326, 0}
{327, 58664034}
{328, 0}
{329, 0}
{330, 0}
{331, -71545318}
{332, 0}
{333, -65031174}
{334, 0}
{335, 0}
{336, 31629312}
{337, -52240606}
{338, 0}
{339, 0}
{340, 0}
{341, 0}
{342, 0}
{343, 43901572}
{344, 0}
{345, 0}
{346, 0}
{347, 0}
{348, 0}
{349, 56926298}
{350, 0}
{351, -9959598}
{352, 0}
{353, 0}
{354, 0}
{355, 0}
{356, 0}
{357, 0}
{358, 0}
{359, 0}
{360, 0}
{361, 64932843}
{362, 0}
{363, -47832147}
{364, -9261824}
{365, 0}
{366, 0}
{367, -80026126}
{368, 0}
{369, 0}
{370, 0}
{371, 0}
{372, -60967296}
{373, 48732266}
{374, 0}
{375, 0}
{376, 0}
{377, 0}
{378, 0}
{379, -35194822}
{380, 0}
{381, 106713882}
{382, 0}
{383, 0}
{384, 0}
{385, 0}
{386, 0}
{387, 81200394}
{388, -3612544}
{389, 0}
{390, 0}
{391, 0}
{392, 0}
{393, 0}
{394, 0}
{395, 0}
{396, 0}
{397, -123725446}
{398, 0}
{399, -81714204}
{400, 64000000}
{401, 0}
{402, 0}
{403, 17852692}
{404, 0}
{405, 0}
{406, 0}
{407, 0}
{408, 0}
{409, -68839342}
{410, 0}
{411, 0}
{412, 72124544}
{413, 0}
{414, 0}
{415, 0}
{416, 0}
{417, -34142526}
{418, 0}
{419, 0}
{420, 0}
{421, 144474122}
{422, 0}
{423, 0}
{424, 0}
{425, 0}
{426, 0}
{427, 120359668}
{428, 0}
{429, 0}
{430, 0}
{431, 0}
{432, -80621568}
{433, -155657374}
{434, 0}
{435, 0}
{436, -139055488}
{437, 0}
{438, 0}
{439, 53516738}
{440, 0}
{441, -26136837}
{442, 0}
{443, 0}
{444, 154147968}
{445, 0}
{446, 0}
{447, 0}
{448, -74973184}
{449, 0}
{450, 0}
{451, 0}
{452, 0}
{453, 103420746}
{454, 0}
{455, 0}
{456, 0}
{457, -29343886}
{458, 0}
{459, 0}
{460, 0}
{461, 0}
{462, 0}
{463, 192742706}
{464, 0}
{465, 0}
{466, 0}
{467, 0}
{468, 23607936}
{469, -49441964}
{470, 0}
{471, -191233278}
{472, 0}
{473, 0}
{474, 0}
{475, -165343750}
{476, 0}
{477, 0}
{478, 0}
{479, 0}
{480, 0}
{481, -45138236}
{482, 0}
{483, 0}
{484, 113379904}
{485, 0}
{486, 0}
{487, 205807394}
{488, 0}
{489, -78259662}
{490, 0}
{491, 0}
{492, 0}
{493, 0}
{494, 0}
{495, 0}
{496, 144515072}
{497, 0}
{498, 0}
{499, -19404502}
{500, 0}
{501, 0}
{502, 0}
{503, 0}
{504, 0}
{505, 0}
{506, 0}
{507, 123410871}
{508, -252951424}
{509, 0}
{510, 0}
{511, -182486876}
{512, 0}
{513, 208285506}
{514, 0}
{515, 0}
{516, -192475008}
{517, 0}
{518, 0}
{519, 0}
{520, 0}
{521, 0}
{522, 0}
{523, -141149734}
{524, 0}
{525, 120656250}
{526, 0}
{527, 0}
{528, 0}
{529, 148035889}
{530, 0}
{531, 0}
{532, 193692928}
{533, 0}
{534, 0}
{535, 0}
{536, 0}
{537, 0}
{538, 0}
{539, 0}
{540, 0}
{541, 197610842}
{542, 0}
{543, -2653614}
{544, 0}
{545, 0}
{546, 0}
{547, -324645046}
{548, 0}
{549, -306790902}
{550, 0}
{551, 0}
{552, 0}
{553, 58521892}
{554, 0}
{555, 0}
{556, 80930432}
{557, 0}
{558, 0}
{559, 56361316}
{560, 0}
{561, 0}
{562, 0}
{563, 0}
{564, 0}
{565, 0}
{566, 0}
{567, -151992126}
{568, 0}
{569, 0}
{570, 0}
{571, 171110522}
{572, 0}
{573, 0}
{574, 0}
{575, 0}
{576, 191102976}
{577, -70555966}
{578, 0}
{579, 352501578}
{580, 0}
{581, 0}
{582, 0}
{583, 0}
{584, 0}
{585, 0}
{586, 0}
{587, 0}
{588, 61953984}
{589, -373354124}
{590, 0}
{591, 0}
{592, -365387776}
{593, 0}
{594, 0}
{595, 0}
{596, 0}
{597, -314671446}
{598, 0}
{599, 0}
{600, 0}
{601, 424443602}
{602, 0}
{603, 126025146}
{604, -245145472}
{605, 0}
{606, 0}
{607, 360399314}
{608, 0}
{609, 0}
{610, 0}
{611, 0}
{612, 0}
{613, -158280694}
{614, 0}
{615, 0}
{616, 0}
{617, 0}
{618, 0}
{619, 236189018}
{620, 0}
{621, 0}
{622, 0}
{623, 0}
{624, -55959552}
{625, 244140625}
{626, 0}
{627, 0}
{628, 453293696}
{629, 0}
{630, 0}
{631, -498899518}
{632, 0}
{633, -475123374}
{634, 0}
{635, 0}
{636, 0}
{637, -18141618}
{638, 0}
{639, 0}
{640, 0}
{641, 0}
{642, 0}
{643, -358509814}
{644, 0}
{645, 0}
{646, 0}
{647, 0}
{648, 0}
{649, 0}
{650, 0}
{651, 272447604}
{652, 185504384}
{653, 0}
{654, 0}
{655, 0}
{656, 0}
{657, 465150114}
{658, 0}
{659, 0}
{660, 0}
{661, -158097238}
{662, 0}
{663, 0}
{664, 0}
{665, 0}
{666, 0}
{667, 0}
{668, 0}
{669, 318889818}
{670, 0}
{671, 0}
{672, 0}
{673, -31239934}
{674, 0}
{675, -307546875}
{676, -292529472}
{677, 0}
{678, 0}
{679, 16143556}
{680, 0}
{681, 0}
{682, 0}
{683, 0}
{684, -493713792}
{685, 0}
{686, 0}
{687, 109966194}
{688, 456237056}
{689, 0}
{690, 0}
{691, -401569558}
{692, 0}
{693, 0}
{694, 0}
{695, 0}
{696, 0}
{697, 0}
{698, 0}
{699, 0}
{700, -286000000}
{701, 0}
{702, 0}
{703, 943977892}
{704, 0}
{705, 0}
{706, 0}
{707, 0}
{708, 0}
{709, 593731658}
{710, 0}
{711, -149169438}
{712, 0}
{713, 0}
{714, 0}
{715, 0}
{716, 0}
{717, 0}
{718, 0}
{719, 0}
{720, 0}
{721, -322306556}
{722, 0}
{723, -713875734}
{724, 6290048}
{725, 0}
{726, 0}
{727, -652272766}
{728, 0}
{729, 387420489}
{730, 0}
{731, 0}
{732, 727208064}
{733, -561163174}
{734, 0}
{735, 0}
{736, 0}
{737, 0}
{738, 0}
{739, 177286538}
{740, 0}
{741, 144571284}
{742, 0}
{743, 0}
{744, 0}
{745, 0}
{746, 0}
{747, 0}
{748, 0}
{749, 0}
{750, 0}
{751, -297133198}
{752, 0}
{753, 0}
{754, 0}
{755, 0}
{756, 360277632}
{757, 852164714}
{758, 0}
{759, 0}
{760, 0}
{761, 0}
{762, 0}
{763, 621404212}
{764, 0}
{765, 0}
{766, 0}
{767, 0}
{768, -452984832}
{769, -888297982}
{770, 0}
{771, 0}
{772, -835559296}
{773, 0}
{774, 0}
{775, 551281250}
{776, 0}
{777, -688848732}
{778, 0}
{779, 0}
{780, 0}
{781, 0}
{782, 0}
{783, 0}
{784, -146853888}
{785, 0}
{786, 0}
{787, 908673194}
{788, 0}
{789, 0}
{790, 0}
{791, 0}
{792, 0}
{793, -212944028}
{794, 0}
{795, 0}
{796, 745887872}
{797, 0}
{798, 0}
{799, 0}
{800, 0}
{801, 0}
{802, 0}
{803, 0}
{804, -298726272}
{805, 0}
{806, 0}
{807, 0}
{808, 0}
{809, 0}
{810, 0}
{811, 483015962}
{812, 0}
{813, 1056933306}
{814, 0}
{815, 0}
{816, 0}
{817, -1178686652}
{818, 0}
{819, -105497964}
{820, 0}
{821, 0}
{822, 0}
{823, -965555134}
{824, 0}
{825, 0}
{826, 0}
{827, 0}
{828, 0}
{829, -848197222}
{830, 0}
{831, 709208082}
{832, 132644864}
{833, 0}
{834, 0}
{835, 0}
{836, 0}
{837, -694455606}
{838, 0}
{839, 0}
{840, 0}
{841, 594823321}
{842, 0}
{843, 0}
{844, 1126218368}
{845, 0}
{846, 0}
{847, -506666446}
{848, 0}
{849, 377200098}
{850, 0}
{851, 0}
{852, 0}
{853, 938655146}
{854, 0}
{855, 0}
{856, 0}
{857, 0}
{858, 0}
{859, -287739142}
{860, 0}
{861, 0}
{862, 0}
{863, 0}
{864, 0}
{865, 0}
{866, 0}
{867, -651714363}
{868, -645801728}
{869, 0}
{870, 0}
{871, 87474244}
{872, 0}
{873, -41149134}
{874, 0}
{875, 0}
{876, -1102578048}
{877, 1165970234}
{878, 0}
{879, 0}
{880, 0}
{881, 0}
{882, 0}
{883, -949268374}
{884, 0}
{885, 0}
{886, 0}
{887, 0}
{888, 0}
{889, 1130376676}
{890, 0}
{891, 0}
{892, -755886976}
{893, 0}
{894, 0}
{895, 0}
{896, 0}
{897, 0}
{898, 0}
{899, 0}
{900, 729000000}
{901, 0}
{902, 0}
{903, 860122692}
{904, 0}
{905, 0}
{906, 0}
{907, 518340314}
{908, 0}
{909, 0}
{910, 0}
{911, 0}
{912, 1170284544}
{913, 0}
{914, 0}
{915, 0}
{916, -260660608}
{917, 0}
{918, 0}
{919, -1544707582}
{920, 0}
{921, -1494199278}
{922, 0}
{923, 0}
{924, 0}
{925, -1393843750}
{926, 0}
{927, 821543634}
{928, 0}
{929, 0}
{930, 0}
{931, 379396446}
{932, 0}
{933, 0}
{934, 0}
{935, 0}
{936, 0}
{937, 1436046194}
{938, 0}
{939, -1049530662}
{940, 0}
{941, 0}
{942, 0}
{943, 0}
{944, 0}
{945, 0}
{946, 0}
{947, 0}
{948, 353586816}
{949, 322861396}
{950, 0}
{951, 0}
{952, 0}
{953, 0}
{954, 0}
{955, 0}
{956, 0}
{957, 0}
{958, 0}
{959, 0}
{960, 0}
{961, 357315843}
{962, 0}
{963, 0}
{964, 1692149888}
{965, 0}
{966, 0}
{967, 693538274}
{968, 0}
{969, 0}
{970, 0}
{971, 0}
{972, -918330048}
{973, -361657868}
{974, 0}
{975, -213468750}
{976, -1723752448}
{977, 0}
{978, 0}
{979, 0}
{980, 0}
{981, -1583928918}
{982, 0}
{983, 0}
{984, 0}
{985, 0}
{986, 0}
{987, 0}
{988, -342687488}
{989, 0}
{990, 0}
{991, 135429842}
{992, 0}
{993, 1931723586}
{994, 0}
{995, 0}
{996, 0}
{997, -1146265846}
{998, 0}
{999, 1755841698}
{1000, 1000}