{1, 1}
{2, 8}
{3, 27}
{4, 64}
{5, -114}
{6, 216}
{7, -1576}
{8, 512}
{9, 729}
{10, -912}
{11, 7332}
{12, 1728}
{13, -3802}
{14, -12608}
{15, -3078}
{16, 4096}
{17, -6606}
{18, 5832}
{19, 24860}
{20, -7296}
{21, -42552}
{22, 58656}
{23, 41448}
{24, 13824}
{25, -65129}
{26, -30416}
{27, 19683}
{28, -100864}
{29, -41610}
{30, -24624}
{31, 33152}
{32, 32768}
{33, 197964}
{34, -52848}
{35, 179664}
{36, 46656}
{37, -36466}
{38, 198880}
{39, -102654}
{40, -58368}
{41, -639078}
{42, -340416}
{43, -156412}
{44, 469248}
{45, -83106}
{46, 331584}
{47, -433776}
{48, 110592}
{49, 1660233}
{50, -521032}
{51, -178362}
{52, -243328}
{53, 786078}
{54, 157464}
{55, -835848}
{56, -806912}
{57, 671220}
{58, -332880}
{59, 745140}
{60, -196992}
{61, -1660618}
{62, 265216}
{63, -1148904}
{64, 262144}
{65, 433428}
{66, 1583712}
{67, -3290836}
{68, -422784}
{69, 1119096}
{70, 1437312}
{71, 5716152}
{72, 373248}
{73, 2659898}
{74, -291728}
{75, -1758483}
{76, 1591040}
{77, -11555232}
{78, -821232}
{79, 3807440}
{80, -466944}
{81, 531441}
{82, -5112624}
{83, 2229468}
{84, -2723328}
{85, 753084}
{86, -1251296}
{87, -1123470}
{88, 3753984}
{89, 5991210}
{90, -664848}
{91, 5991952}
{92, 2652672}
{93, 895104}
{94, -3470208}
{95, -2834040}
{96, 884736}
{97, -4060126}
{98, 13281864}
{99, 5345028}
{100, -4168256}
{101, -17281938}
{102, -1426896}
{103, -14362312}
{104, -1946624}
{105, 4850928}
{106, 6288624}
{107, 6454404}
{108, 1259712}
{109, -884410}
{110, -6686784}
{111, -984582}
{112, -6455296}
{113, 12132498}
{114, 5369760}
{115, -4725072}
{116, -2663040}
{117, -2771658}
{118, 5961120}
{119, 10411056}
{120, -1575936}
{121, 34271053}
{122, -13284944}
{123, -17255106}
{124, 2121728}
{125, 16330956}
{126, -9191232}
{127, 6868064}
{128, 2097152}
{129, -4223124}
{130, 3467424}
{131, -39520788}
{132, 12669696}
{133, -39179360}
{134, -26326688}
{135, -2243862}
{136, -3382272}
{137, 19174074}
{138, 8952768}
{139, 13244900}
{140, 11498496}
{141, -11711952}
{142, 45729216}
{143, -27876264}
{144, 2985984}
{145, 4743540}
{146, 21279184}
{147, 44826291}
{148, -2333824}
{149, 57362430}
{150, -14067864}
{151, -31087288}
{152, 12728320}
{153, -4815774}
{154, -92441856}
{155, -3779328}
{156, -6569856}
{157, -33783466}
{158, 30459520}
{159, 21224106}
{160, -3735552}
{161, -65322048}
{162, 4251528}
{163, 62665868}
{164, -40900992}
{165, -22567896}
{166, 17835744}
{167, 62707224}
{168, -21786624}
{169, -48293313}
{170, 6024672}
{171, 18122940}
{172, -10010368}
{173, -27052122}
{174, -8987760}
{175, 102643304}
{176, 30031872}
{177, 20118780}
{178, 47929680}
{179, -134280900}
{180, -5318784}
{181, 114660542}
{182, 47935616}
{183, -44836686}
{184, 21221376}
{185, 4157124}
{186, 7160832}
{187, -48435192}
{188, -27761664}
{189, -31020408}
{190, -22672320}
{191, 16360512}
{192, 7077888}
{193, -154198462}
{194, -32481008}
{195, 11702556}
{196, 106254912}
{197, 83228814}
{198, 42760224}
{199, -76172200}
{200, -33346048}
{201, -88852572}
{202, -138255504}
{203, 65577360}
{204, -11415168}
{205, 72854892}
{206, -114898496}
{207, 30215592}
{208, -15572992}
{209, 182273520}
{210, 38807424}
{211, 35244572}
{212, 50308992}
{213, 154336104}
{214, 51635232}
{215, 17830968}
{216, 10077696}
{217, -52247552}
{218, -7075280}
{219, 71817246}
{220, -53494272}
{221, 25116012}
{222, -7876656}
{223, -189131392}
{224, -51642368}
{225, -47479041}
{226, 97059984}
{227, -176100276}
{228, 42958080}
{229, 65039630}
{230, -37800576}
{231, -311991264}
{232, -21304320}
{233, -251318502}
{234, -22173264}
{235, 49450464}
{236, 47688960}
{237, 102800880}
{238, 83288448}
{239, 213079440}
{240, -12607488}
{241, 257283602}
{242, 274168424}
{243, 14348907}
{244, -106279552}
{245, -189266562}
{246, -138040848}
{247, -94517720}
{248, 16973824}
{249, 60195636}
{250, 130647648}
{251, 123057972}
{252, -73529856}
{253, 303896736}
{254, 54944512}
{255, 20333268}
{256, 16777216}
{257, -443333886}
{258, -33784992}
{259, 57470416}
{260, 27739392}
{261, -30333690}
{262, -316166304}
{263, 298924728}
{264, 101357568}
{265, -89612892}
{266, -313434880}
{267, 161762670}
{268, -210613504}
{269, 208907910}
{270, -17950896}
{271, -11274928}
{272, -27058176}
{273, 161782704}
{274, 153392592}
{275, -477525828}
{276, 71622144}
{277, -658964386}
{278, 105959200}
{279, 24167808}
{280, 91987968}
{281, -105122838}
{282, -93695616}
{283, 330161108}
{284, 365833728}
{285, -76519080}
{286, -223010112}
{287, 1007186928}
{288, 23887872}
{289, -366699437}
{290, 37948320}
{291, -109623402}
{292, 170233472}
{293, -87100242}
{294, 358610328}
{295, -84945960}
{296, -18670592}
{297, 144315756}
{298, 458899440}
{299, -157585296}
{300, -112542912}
{301, 246505312}
{302, -248698304}
{303, -466612326}
{304, 101826560}
{305, 189310452}
{306, -38526192}
{307, -391708996}
{308, -739534848}
{309, -387782424}
{310, -30234624}
{311, -204935928}
{312, -52558848}
{313, 877202378}
{314, -270267728}
{315, 130975056}
{316, 243676160}
{317, -440830506}
{318, 169792848}
{319, -305084520}
{320, -29884416}
{321, 174268908}
{322, -522576384}
{323, -164225160}
{324, 34012224}
{325, 247620458}
{326, 501326944}
{327, -23879070}
{328, -327207936}
{329, 683630976}
{330, -180543168}
{331, 1112230052}
{332, 142685952}
{333, -26583714}
{334, 501657792}
{335, 375155304}
{336, -174292992}
{337, 288198194}
{338, -386346504}
{339, 327577446}
{340, 48197376}
{341, 243070464}
{342, 144983520}
{343, -1318623440}
{344, -80082944}
{345, -127576944}
{346, -216416976}
{347, -1106006316}
{348, -71902080}
{349, -1321843690}
{350, 821146432}
{351, -74834766}
{352, 240254976}
{353, 1203951138}
{354, 160950240}
{355, -651641328}
{356, 383437440}
{357, 281098512}
{358, -1074247200}
{359, -1320572520}
{360, -42550272}
{361, -275852139}
{362, 917284336}
{363, 925318431}
{364, 383484928}
{365, -303228372}
{366, -358693488}
{367, 1751069744}
{368, 169771008}
{369, -465887862}
{370, 33256992}
{371, -1238858928}
{372, 57286656}
{373, -487945282}
{374, -387481536}
{375, 440935812}
{376, -222093312}
{377, 158201220}
{378, -248163264}
{379, 1110068660}
{380, -181378560}
{381, 185437728}
{382, 130884096}
{383, 1869115008}
{384, 56623104}
{385, 1317296448}
{386, -1233587696}
{387, -114024348}
{388, -259848064}
{389, -273895410}
{390, 93620448}
{391, -273805488}
{392, 850039296}
{393, -1067061276}
{394, 665830512}
{395, -434048160}
{396, 342081792}
{397, 624551654}
{398, -609377600}
{399, -1057842720}
{400, -266768384}
{401, 555500082}
{402, -710820576}
{403, -126043904}
{404, -1106044032}
{405, -60584274}
{406, 524618880}
{407, -267368712}
{408, -91321344}
{409, -2157700630}
{410, 582839136}
{411, 517699998}
{412, -919187968}
{413, -1174340640}
{414, 241724736}
{415, -254159352}
{416, -124583936}
{417, 357612300}
{418, 1458188160}
{419, 1677967500}
{420, 310459392}
{421, -525233458}
{422, 281956576}
{423, -316222704}
{424, 402471936}
{425, 430242174}
{426, 1234688832}
{427, 2617133968}
{428, 413081856}
{429, -752659128}
{430, 142647744}
{431, 170592912}
{432, 80621568}
{433, -1687969582}
{434, -417980416}
{435, 128075580}
{436, -56602240}
{437, 1030397280}
{438, 574537968}
{439, -1178496280}
{440, -427954176}
{441, 1210309857}
{442, 200928096}
{443, 715754868}
{444, -63013248}
{445, -682997940}
{446, -1513051136}
{447, 1548785610}
{448, -413138944}
{449, -1373583870}
{450, -379832328}
{451, -4685719896}
{452, 776479872}
{453, -839356776}
{454, -1408802208}
{455, -683082528}
{456, 343664640}
{457, 1847520314}
{458, 520317040}
{459, -130025898}
{460, -302404608}
{461, 3094137222}
{462, -2495930112}
{463, 3004508048}
{464, -170434560}
{465, -102041856}
{466, -2010548016}
{467, -2992515876}
{468, -177386112}
{469, 5186357536}
{470, 395603712}
{471, -912153582}
{472, 381511680}
{473, -1146812784}
{474, 822407040}
{475, -1619106940}
{476, 666307584}
{477, 573050862}
{478, 1704635520}
{479, 1840414560}
{480, -100859904}
{481, 138643732}
{482, 2058268816}
{483, -1763695296}
{484, 2193347392}
{485, 462854364}
{486, 114791256}
{487, -426675976}
{488, -850236416}
{489, 1691978436}
{490, -1514132496}
{491, 60754692}
{492, -1104326784}
{493, 274875660}
{494, -756141760}
{495, -609333192}
{496, 135790592}
{497, -9008655552}
{498, 481565088}
{499, 3245877500}
{500, 1045181184}
{501, 1693095048}
{502, 984463776}
{503, -744381432}
{504, -588238848}
{505, 1970140932}
{506, 2431173888}
{507, -1303919451}
{508, 439556096}
{509, -444155370}
{510, 162666144}
{511, -4191999248}
{512, 134217728}
{513, 489319380}
{514, -3546671088}
{515, 1637303568}
{516, -270279936}
{517, -3180445632}
{518, 459763328}
{519, -730407294}
{520, 221915136}
{521, 3049626042}
{522, -242669520}
{523, -1403064412}
{524, -2529330432}
{525, 2771369208}
{526, 2391397824}
{527, -219002112}
{528, 810860544}
{529, -1686888743}
{530, -716903136}
{531, 543207060}
{532, -2507479040}
{533, 2429774556}
{534, 1294101360}
{535, -735802056}
{536, -1684908032}
{537, -3625584300}
{538, 1671263280}
{539, 12172828356}
{540, -143607168}
{541, 4211059862}
{542, -90199424}
{543, 3095834634}
{544, -216465408}
{545, 100822740}
{546, 1294261632}
{547, 1999559564}
{548, 1227140736}
{549, -1210590522}
{550, -3820206624}
{551, -1034424600}
{552, 572977152}
{553, -6000525440}
{554, -5271715088}
{555, 112242348}
{556, 847673600}
{557, -3374032986}
{558, 193342464}
{559, 594678424}
{560, 735903744}
{561, -1307750184}
{562, -840982704}
{563, -5580213252}
{564, -749564928}
{565, -1383104772}
{566, 2641288864}
{567, -837551016}
{568, 2926669824}
{569, -888309750}
{570, -612152640}
{571, -1791706828}
{572, -1784080896}
{573, 441733824}
{574, 8057495424}
{575, -2699466792}
{576, 191102976}
{577, 3821026754}
{578, -2933595496}
{579, -4163358474}
{580, 303586560}
{581, -3513641568}
{582, -876987216}
{583, 5763523896}
{584, 1361867776}
{585, 315969012}
{586, -696801936}
{587, 4362188964}
{588, 2868882624}
{589, 824158720}
{590, -679567680}
{591, 2247177978}
{592, -149364736}
{593, 6385307058}
{594, 1154526048}
{595, -1186860384}
{596, 3671195520}
{597, -2056649400}
{598, -1260682368}
{599, 804297000}
{600, -900343296}
{601, -4871616598}
{602, 1972042496}
{603, -2399019444}
{604, -1989586432}
{605, -3906900042}
{606, -3732898608}
{607, 7175168384}
{608, 814612480}
{609, 1770588720}
{610, 1514483616}
{611, 1649216352}
{612, -308209536}
{613, 3478905038}
{614, -3133671968}
{615, 1967082084}
{616, -5916278784}
{617, -239378406}
{618, -3102259392}
{619, -5529588220}
{620, -241876992}
{621, 815820984}
{622, -1639487424}
{623, -9442146960}
{624, -420470784}
{625, 3226474141}
{626, 7017619024}
{627, 4921385040}
{628, -2162141824}
{629, 240894396}
{630, 1047800448}
{631, -6136833688}
{632, 1949409280}
{633, 951603444}
{634, -3526644048}
{635, -782959296}
{636, 1358342784}
{637, -6312205866}
{638, -2440676160}
{639, 4167074808}
{640, -239075328}
{641, 10703801922}
{642, 1394151264}
{643, -1398026452}
{644, -4180611072}
{645, 481436136}
{646, -1313801280}
{647, -5316047496}
{648, 272097792}
{649, 5463366480}
{650, 1980963664}
{651, -1410683904}
{652, 4010615552}
{653, 3244034118}
{654, -191032560}
{655, 4505369832}
{656, -2617663488}
{657, 1939065642}
{658, 5469047808}
{659, -5165059620}
{660, -1444345344}
{661, -3225154018}
{662, 8897840416}
{663, 678132324}
{664, 1141487616}
{665, 4466447040}
{666, -212669712}
{667, -1724651280}
{668, 4013262336}
{669, -5106547584}
{670, 3001242432}
{671, -12175651176}
{672, -1394343936}
{673, -2006334622}
{674, 2305585552}
{675, -1281934107}
{676, -3090772032}
{677, 10021103214}
{678, 2620619568}
{679, 6398758576}
{680, 385579008}
{681, -4754707452}
{682, 1944563712}
{683, -5848606332}
{684, 1159868160}
{685, -2185844436}
{686, -10548987520}
{687, 1756070010}
{688, -640663552}
{689, -2988668556}
{690, -1020615552}
{691, 2586855932}
{692, -1731335808}
{693, -8423764128}
{694, -8848050528}
{695, -1509918600}
{696, -575216640}
{697, 4221749268}
{698, -10574749520}
{699, -6785599554}
{700, 6569171456}
{701, -1744599978}
{702, -598678128}
{703, -906544760}
{704, 1922039808}
{705, 1335162528}
{706, 9631609104}
{707, 27236334288}
{708, 1287601920}
{709, -11205076690}
{710, -5213130624}
{711, 2775623760}
{712, 3067499520}
{713, 1374084096}
{714, 2248788096}
{715, 3177894096}
{716, -8593977600}
{717, 5753144880}
{718, -10564580160}
{719, -936568080}
{720, -340402176}
{721, 22635003712}
{722, -2206817112}
{723, 6946657254}
{724, 7338274688}
{725, 2710017690}
{726, 7402547448}
{727, 4204452104}
{728, 3067879424}
{729, 387420489}
{730, -2425826976}
{731, 1033257672}
{732, -2869547904}
{733, -11549138602}
{734, 14008557952}
{735, -5110197174}
{736, 1358168064}
{737, -24128409552}
{738, -3727102896}
{739, -13965501940}
{740, 266055936}
{741, -2551978440}
{742, -9910871424}
{743, 14383247448}
{744, 458293248}
{745, -6539317020}
{746, -3903562256}
{747, 1625282172}
{748, -3099852288}
{749, -10172140704}
{750, 3527486496}
{751, -670840528}
{752, -1776746496}
{753, 3322565244}
{754, 1265609760}
{755, 3543950832}
{756, -1985306112}
{757, -19156941826}
{758, 8880549280}
{759, 8205211872}
{760, -1451028480}
{761, 17911981002}
{762, 1483501824}
{763, 1393830160}
{764, 1047072768}
{765, 548998236}
{766, 14952920064}
{767, -2833022280}
{768, 452984832}
{769, -21407177470}
{770, 10538371584}
{771, -11970014922}
{772, -9868701568}
{773, -755162802}
{774, -912194784}
{775, -2159156608}
{776, -2078784512}
{777, 1551701232}
{778, -2191163280}
{779, -15887479080}
{780, 748963584}
{781, 41910826464}
{782, -2190443904}
{783, -819009630}
{784, 6800314368}
{785, 3851315124}
{786, -8536490208}
{787, 20466541724}
{788, 5326644096}
{789, 8070967656}
{790, -3472385280}
{791, -19120816848}
{792, 2736654336}
{793, 6313669636}
{794, 4996413232}
{795, -2419548084}
{796, -4875020800}
{797, -10309775946}
{798, -8462741760}
{799, 2865524256}
{800, -2134147072}
{801, 4367592090}
{802, 4444000656}
{803, 19502372136}
{804, -5686564608}
{805, 7446713472}
{806, -1008351232}
{807, 5640513570}
{808, -8848352256}
{809, -416427750}
{810, -484674192}
{811, -5826870268}
{812, 4196951040}
{813, -304423056}
{814, -2138949696}
{815, -7143908952}
{816, -730570752}
{817, -3888402320}
{818, -17261605040}
{819, 4368133008}
{820, 4662713088}
{821, -20833271778}
{822, 4141599984}
{823, 4234025768}
{824, -7353503744}
{825, -12893197356}
{826, -9394725120}
{827, 5705967924}
{828, 1933797888}
{829, 25161237110}
{830, -2033274816}
{831, -17792038422}
{832, -996671488}
{833, -10967499198}
{834, 2860898400}
{835, -7148623536}
{836, 11665505280}
{837, 652530816}
{838, 13423740000}
{839, 22704795960}
{840, 2483675136}
{841, -15518484209}
{842, -4201867664}
{843, -2838316626}
{844, 2255652608}
{845, 5505437682}
{846, -2529781632}
{847, -54011179528}
{848, 3219775488}
{849, 8914349916}
{850, 3441937392}
{851, -1511442768}
{852, 9877510656}
{853, 28687212638}
{854, 20937071744}
{855, -2066015160}
{856, 3304654848}
{857, 5349500394}
{858, -6021273024}
{859, -14032979500}
{860, 1141181952}
{861, 27194047056}
{862, 1364743296}
{863, 32499400608}
{864, 644972544}
{865, 3083941908}
{866, -13503756656}
{867, -9900884799}
{868, -3343843328}
{869, 27916150080}
{870, 1024604640}
{871, 12511758472}
{872, -452817920}
{873, -2959831854}
{874, 8243178240}
{875, -25737586656}
{876, 4596303744}
{877, -33869400826}
{878, -9427970240}
{879, -2351706534}
{880, -3423633408}
{881, -15270829038}
{882, 9682478856}
{883, -11204511172}
{884, 1607424768}
{885, -2293540920}
{886, 5726038944}
{887, 6972321864}
{888, -504105984}
{889, -10824068864}
{890, -5463983520}
{891, 3896525412}
{892, -12104409088}
{893, -10783671360}
{894, 12390284880}
{895, 15308022600}
{896, -3305111552}
{897, -4254802992}
{898, -10988670960}
{899, -1379454720}
{900, -3038658624}
{901, -5192831268}
{902, -37485759168}
{903, 6655643424}
{904, 6211838976}
{905, -13071301788}
{906, -6714854208}
{907, 1180948004}
{908, -11270417664}
{909, -12598532802}
{910, -5464660224}
{911, 12791515632}
{912, 2749317120}
{913, 16346459376}
{914, 14780162512}
{915, 5111382204}
{916, 4162536320}
{917, 62284761888}
{918, -1040207184}
{919, 35235279560}
{920, -2419236864}
{921, -10576142892}
{922, 24753097776}
{923, -21732809904}
{924, -19967440896}
{925, 2374994114}
{926, 24036064384}
{927, -10470125448}
{928, -1363476480}
{929, -21776443230}
{930, -816334848}
{931, 41273392380}
{932, -16084384128}
{933, -5533270056}
{934, -23940127008}
{935, 5521611888}
{936, -1419088896}
{937, 11579464154}
{938, 41490860288}
{939, 23684464206}
{940, 3164829696}
{941, -38393035098}
{942, -7297228656}
{943, -26488504944}
{944, 3052093440}
{945, 3536326512}
{946, -9174502272}
{947, 11184090684}
{948, 6579256320}
{949, -10112932196}
{950, -12952855520}
{951, -11902423662}
{952, 5330460672}
{953, -5198349942}
{954, 4584406896}
{955, -1865098368}
{956, 13637084160}
{957, -8237282040}
{958, 14723316480}
{959, -30218340624}
{960, -806879232}
{961, -26413559007}
{962, 1109149856}
{963, 4705260516}
{964, 16466150528}
{965, 17578624668}
{966, -14109562368}
{967, -269243176}
{968, 17546779136}
{969, -4434079320}
{970, 3702834912}
{971, 4372831332}
{972, 918330048}
{973, -20873962400}
{974, -3413407808}
{975, 6685752366}
{976, -6801891328}
{977, -37499076366}
{978, 13535827488}
{979, 43927551720}
{980, -12113059968}
{981, -644734890}
{982, 486037536}
{983, -30618970392}
{984, -8834614272}
{985, -9488084796}
{986, 2199005280}
{987, 18458036352}
{988, -6049134080}
{989, -6482964576}
{990, -4874665536}
{991, -17270335168}
{992, 1086324736}
{993, 30030211404}
{994, -72069244416}
{995, 8683630800}
{996, 3852520704}
{997, -3750774706}
{998, 25967020000}
{999, -717760278}
{1000, 8361449472}