{1, 1}
{2, 6}
{3, -27}
{4, -92}
{5, 390}
{6, -162}
{7, -64}
{8, -1320}
{9, 729}
{10, 2340}
{11, -948}
{12, 2484}
{13, -5098}
{14, -384}
{15, -10530}
{16, 3856}
{17, 28386}
{18, 4374}
{19, -8620}
{20, -35880}
{21, 1728}
{22, -5688}
{23, -15288}
{24, 35640}
{25, 73975}
{26, -30588}
{27, -19683}
{28, 5888}
{29, 36510}
{30, -63180}
{31, -276808}
{32, 192096}
{33, 25596}
{34, 170316}
{35, -24960}
{36, -67068}
{37, 268526}
{38, -51720}
{39, 137646}
{40, -514800}
{41, -629718}
{42, 10368}
{43, 685772}
{44, 87216}
{45, 284310}
{46, -91728}
{47, 583296}
{48, -104112}
{49, -819447}
{50, 443850}
{51, -766422}
{52, 469016}
{53, -428058}
{54, -118098}
{55, -369720}
{56, 84480}
{57, 232740}
{58, 219060}
{59, 1306380}
{60, 968760}
{61, 300662}
{62, -1660848}
{63, -46656}
{64, 659008}
{65, -1988220}
{66, 153576}
{67, -507244}
{68, -2611512}
{69, 412776}
{70, -149760}
{71, 5560632}
{72, -962280}
{73, 1369082}
{74, 1611156}
{75, -1997325}
{76, 793040}
{77, 60672}
{78, 825876}
{79, -6913720}
{80, 1503840}
{81, 531441}
{82, -3778308}
{83, -4376748}
{84, -158976}
{85, 11070540}
{86, 4114632}
{87, -985770}
{88, 1251360}
{89, -8528310}
{90, 1705860}
{91, 326272}
{92, 1406496}
{93, 7473816}
{94, 3499776}
{95, -3361800}
{96, -5186592}
{97, -8826814}
{98, -4916682}
{99, -691092}
{100, -6805700}
{101, 11986422}
{102, -4598532}
{103, 7209392}
{104, 6729360}
{105, 673920}
{106, -2568348}
{107, 11426076}
{108, 1810836}
{109, 4020950}
{110, -2218320}
{111, -7250202}
{112, -246784}
{113, -17706318}
{114, 1396440}
{115, -5962320}
{116, -3358920}
{117, -3716442}
{118, 7838280}
{119, -1816704}
{120, 13899600}
{121, -18588467}
{122, 1803972}
{123, 17002386}
{124, 25466336}
{125, -1618500}
{126, -279936}
{127, 16788296}
{128, -20634240}
{129, -18515844}
{130, -11929320}
{131, 16826772}
{132, -2354832}
{133, 551680}
{134, -3043464}
{135, -7676370}
{136, -37469520}
{137, 28044906}
{138, 2476656}
{139, -11827300}
{140, 2296320}
{141, -15748992}
{142, 33363792}
{143, 4832904}
{144, 2811024}
{145, 14238900}
{146, 8214492}
{147, 22125069}
{148, -24704392}
{149, 20784630}
{150, -11983950}
{151, 76112}
{152, 11378400}
{153, 20693394}
{154, 364032}
{155, -107955120}
{156, -12663432}
{157, -32182474}
{158, -41482320}
{159, 11557566}
{160, 74917440}
{161, 978432}
{162, 3188646}
{163, 58343492}
{164, 57934056}
{165, 9982440}
{166, -26260488}
{167, -25836504}
{168, -2280960}
{169, -36758913}
{170, 66423240}
{171, -6283980}
{172, -63091024}
{173, 63520062}
{174, -5914620}
{175, -4734400}
{176, -3655488}
{177, -35272260}
{178, -51169860}
{179, -80955900}
{180, -26156520}
{181, 64503182}
{182, 1957632}
{183, -8117874}
{184, 20180160}
{185, 104725140}
{186, 44842896}
{187, -26909928}
{188, -53663232}
{189, 1259712}
{190, -20170800}
{191, 56827392}
{192, -17793216}
{193, 116376962}
{194, -52960884}
{195, 53681940}
{196, 75389124}
{197, -118816074}
{198, -4146552}
{199, -95010640}
{200, -97647000}
{201, 13695588}
{202, 71918532}
{203, -2336640}
{204, 70510824}
{205, -245590020}
{206, 43256352}
{207, -11144952}
{208, -19657888}
{209, 8171760}
{210, 4043520}
{211, 179246372}
{212, 39381336}
{213, -150137064}
{214, 68556456}
{215, 267451080}
{216, 25981560}
{217, 17715712}
{218, 24125700}
{219, -36965214}
{220, 34014240}
{221, -144711828}
{222, -43501212}
{223, -206536888}
{224, -12294144}
{225, 53927775}
{226, -106237908}
{227, 43395396}
{228, -21412080}
{229, -36193090}
{230, -35773920}
{231, -1638144}
{232, -48193200}
{233, 92234682}
{234, -22298652}
{235, 227485440}
{236, -120186960}
{237, 186670440}
{238, -10900224}
{239, 49846800}
{240, -40603680}
{241, 199374002}
{242, -111530802}
{243, -14348907}
{244, -27660904}
{245, -319584330}
{246, 102014316}
{247, 43944760}
{248, 365386560}
{249, 118172196}
{250, -9711000}
{251, -394677828}
{252, 4292352}
{253, 14493024}
{254, 100729776}
{255, -298904580}
{256, -208158464}
{257, -142885374}
{258, -111095064}
{259, -17185664}
{260, 182916240}
{261, 26615790}
{262, 100960632}
{263, 440240712}
{264, -33786720}
{265, -166942620}
{266, 3310080}
{267, 230264370}
{268, 46666448}
{269, 275404590}
{270, -46058220}
{271, -424669768}
{272, 109456416}
{273, -8809344}
{274, 168269436}
{275, -70128300}
{276, -37975392}
{277, 516158126}
{278, -70963800}
{279, -201793032}
{280, 32947200}
{281, -311042838}
{282, -94493952}
{283, -594308308}
{284, -511578144}
{285, 90768600}
{286, 28997424}
{287, 40301952}
{288, 140037984}
{289, 395426323}
{290, 85433400}
{291, 238323978}
{292, -125955544}
{293, 115514742}
{294, 132750414}
{295, 509488200}
{296, -354454320}
{297, 18659484}
{298, 124707780}
{299, 77938224}
{300, 183753900}
{301, -43889408}
{302, 456672}
{303, -323633394}
{304, -33238720}
{305, 117258180}
{306, 124160364}
{307, -260599804}
{308, -5581824}
{309, -194653584}
{310, -647730720}
{311, 576794712}
{312, -181692720}
{313, -460074358}
{314, -193094844}
{315, -18195840}
{316, 636062240}
{317, 62556126}
{318, 69345396}
{319, -34611480}
{320, 257013120}
{321, -308504052}
{322, 5870592}
{323, -244687320}
{324, -48892572}
{325, -377124550}
{326, 350060952}
{327, -108565650}
{328, 831227760}
{329, -37330944}
{330, 59894640}
{331, 684235772}
{332, 402660816}
{333, 195755454}
{334, -155019024}
{335, -197825160}
{336, 6663168}
{337, -626312974}
{338, -220553478}
{339, 478070586}
{340, -1018489680}
{341, 262413984}
{342, -37703880}
{343, 105151360}
{344, -905219040}
{345, 160982640}
{346, 381120372}
{347, -1253396004}
{348, 90690840}
{349, 265350230}
{350, -28406400}
{351, 100343934}
{352, -182107008}
{353, -569635518}
{354, -211633560}
{355, 2168646480}
{356, 784604520}
{357, 49051008}
{358, -485735400}
{359, 932540760}
{360, -375289200}
{361, -819567339}
{362, 387019092}
{363, 501888609}
{364, -30017024}
{365, 533941980}
{366, -48707244}
{367, -852564664}
{368, -58950528}
{369, -459064422}
{370, 628350840}
{371, 27395712}
{372, -687591072}
{373, 381183422}
{374, -161459568}
{375, 43699500}
{376, -769950720}
{377, -186127980}
{378, 7558272}
{379, -1483530820}
{380, 309285600}
{381, -453283992}
{382, 340964352}
{383, -761929728}
{384, 557124480}
{385, 23662080}
{386, 698261772}
{387, 499927788}
{388, 812066888}
{389, 1609017990}
{390, 322091640}
{391, -433965168}
{392, 1081670040}
{393, -454322844}
{394, -712896444}
{395, -2696350800}
{396, 63580464}
{397, 1880157926}
{398, -570063840}
{399, -14895360}
{400, 285247600}
{401, 268592322}
{402, 82173528}
{403, 1411167184}
{404, -1102750824}
{405, 207261990}
{406, -14019840}
{407, -254562648}
{408, 1011677040}
{409, 89947850}
{410, -1473540120}
{411, -757212462}
{412, -663264064}
{413, -83608320}
{414, -66869712}
{415, -1706931720}
{416, -979305408}
{417, 319337100}
{418, 49030560}
{419, 1690542660}
{420, -62000640}
{421, -1133327458}
{422, 1075478232}
{423, 425222784}
{424, 565036560}
{425, 2099854350}
{426, -900822384}
{427, -19242368}
{428, -1051198992}
{429, -130488408}
{430, 1604706480}
{431, 2199426912}
{432, -75897648}
{433, -151737838}
{434, 106294272}
{435, -384450300}
{436, -369927400}
{437, 131782560}
{438, -221791284}
{439, 990762560}
{440, 488030400}
{441, -597376863}
{442, -868270968}
{443, -1773756228}
{444, 667018584}
{445, -3326040900}
{446, -1239221328}
{447, -561185010}
{448, -42176512}
{449, -277010190}
{450, 323566650}
{451, 596972664}
{452, 1628981256}
{453, -2055024}
{454, 260372376}
{455, 127246080}
{456, -307216800}
{457, 2947584986}
{458, -217158540}
{459, -558721638}
{460, 548533440}
{461, -2766873378}
{462, -9828864}
{463, 463552952}
{464, 140782560}
{465, 2914788240}
{466, 553408092}
{467, -417921804}
{468, 341912664}
{469, 32463616}
{470, 1364912640}
{471, 868926798}
{472, -1724421600}
{473, -650111856}
{474, 1120022640}
{475, -637664500}
{476, 167136768}
{477, -312054282}
{478, 299080800}
{479, -1509728880}
{480, -2022770880}
{481, -1368945548}
{482, 1196244012}
{483, -26417664}
{484, 1710138964}
{485, -3442457460}
{486, -86093442}
{487, 929459936}
{488, -396873840}
{489, -1575274284}
{490, -1917505980}
{491, 5128027932}
{492, -1564219512}
{493, 1036372860}
{494, 263668560}
{495, -269525880}
{496, -1067371648}
{497, -355880448}
{498, 709033176}
{499, -410649340}
{500, 148902000}
{501, 697585608}
{502, -2368066968}
{503, 5020408872}
{504, 61585920}
{505, 4674704580}
{506, 86958144}
{507, 992490651}
{508, -1544523232}
{509, -3249259170}
{510, -1793427480}
{511, -87621248}
{512, 1392231936}
{513, 169667460}
{514, -857312244}
{515, 2811662880}
{516, 1703457648}
{517, -552964608}
{518, -103113984}
{519, -1715041674}
{520, 2624450400}
{521, -2109501558}
{522, 159694740}
{523, -5289111988}
{524, -1548063024}
{525, 127828800}
{526, 2641444272}
{527, -7857471888}
{528, 98698176}
{529, -3171102503}
{530, -1001655720}
{531, 952351020}
{532, -50754560}
{533, 3210302364}
{534, 1381586220}
{535, 4456169640}
{536, 669562080}
{537, 2185809300}
{538, 1652427540}
{539, 776835756}
{540, 706226040}
{541, 3046135142}
{542, -2548018608}
{543, -1741585914}
{544, 5452837056}
{545, 1568170500}
{546, -52856064}
{547, -4855369564}
{548, -2580131352}
{549, 219182598}
{550, -420769800}
{551, -314716200}
{552, -544864320}
{553, 442478080}
{554, 3096948756}
{555, -2827578780}
{556, 1088111600}
{557, 1277621406}
{558, -1210758192}
{559, -3496065656}
{560, -96245760}
{561, 726568056}
{562, -1866257028}
{563, 4712645172}
{564, 1448907264}
{565, -6905464020}
{566, -3565849848}
{567, -34012224}
{568, -7340034240}
{569, 4577997210}
{570, 544611600}
{571, 4951192172}
{572, -444627168}
{573, -1534339584}
{574, 241811712}
{575, -1130929800}
{576, 480416832}
{577, 8518472066}
{578, 2372557938}
{579, -3142177974}
{580, -1309978800}
{581, 280111872}
{582, 1429943868}
{583, 405798984}
{584, -1807188240}
{585, -1449412380}
{586, 693088452}
{587, -562247364}
{588, -2035506348}
{589, 2386084960}
{590, 3056929200}
{591, 3208033998}
{592, 1035436256}
{593, 3621104082}
{594, 111956904}
{595, -708514560}
{596, -1912185960}
{597, 2565287280}
{598, 467629344}
{599, -7481036760}
{600, 2636469000}
{601, -5812702678}
{602, -263336448}
{603, -369780876}
{604, -7002304}
{605, -7249502130}
{606, -1941800364}
{607, 3840510056}
{608, -1655867520}
{609, 63089280}
{610, 703549080}
{611, -2973643008}
{612, -1903792248}
{613, 1704841742}
{614, -1563598824}
{615, 6630930540}
{616, -80087040}
{617, -2808092454}
{618, -1167921504}
{619, -2543654980}
{620, 9931871040}
{621, 300913704}
{622, 3460768272}
{623, 545811840}
{624, 530762976}
{625, -6410511875}
{626, -2760446148}
{627, -220637520}
{628, 2960787608}
{629, 7622379036}
{630, -109175040}
{631, -151146448}
{632, 9126110400}
{633, -4839652044}
{634, 375336756}
{635, 6547435440}
{636, -1063296072}
{637, 4177540806}
{638, -207668880}
{639, 4053700728}
{640, -8047353600}
{641, -12362510478}
{642, -1851024312}
{643, 2867439812}
{644, -90015744}
{645, -7221179160}
{646, -1468123920}
{647, -4106397384}
{648, -701502120}
{649, -1238448240}
{650, -2262747300}
{651, -478324224}
{652, -5367601264}
{653, 6910997502}
{654, -651393900}
{655, 6562441080}
{656, -2428192608}
{657, 998060778}
{658, -223985664}
{659, 3424439940}
{660, -918384480}
{661, -6764370178}
{662, 4105414632}
{663, 3907219356}
{664, 5777307360}
{665, 215155200}
{666, 1174532724}
{667, -558164880}
{668, 2376958368}
{669, 5576495976}
{670, -1186950960}
{671, -285027576}
{672, 331941888}
{673, -1749591838}
{674, -3757877844}
{675, -1456049925}
{676, 3381819996}
{677, 8300111046}
{678, 2868423516}
{679, 564916096}
{680, -14613112800}
{681, -1171675692}
{682, 1574483904}
{683, -12123151668}
{684, 578126160}
{685, 10937513340}
{686, 630908160}
{687, 977213430}
{688, 2644336832}
{689, 2182239684}
{690, 965895840}
{691, 8218456532}
{692, -5843845704}
{693, 44229888}
{694, -7520376024}
{695, -4612647000}
{696, 1301216400}
{697, -17875175148}
{698, 1592101380}
{699, -2490336414}
{700, 435564800}
{701, 4722309342}
{702, 602063604}
{703, -2314694120}
{704, -624739584}
{705, -6142106880}
{706, -3417813108}
{707, -767131008}
{708, 3245047920}
{709, 2789746910}
{710, 13011878880}
{711, -5040101880}
{712, 11257369200}
{713, 4231840704}
{714, 294306048}
{715, 1884832560}
{716, 7447942800}
{717, -1345863600}
{718, 5595244560}
{719, 1519846560}
{720, 1096299360}
{721, -461401088}
{722, -4917404034}
{723, -5383098054}
{724, -5934292744}
{725, 2700827250}
{726, 3011331654}
{727, -8117607664}
{728, -430679040}
{729, 387420489}
{730, 3203651880}
{731, 19466323992}
{732, 746844408}
{733, -10324065658}
{734, -5115387984}
{735, 8628776910}
{736, -2936763648}
{737, 480867312}
{738, -2754386532}
{739, -13536483820}
{740, -9634712880}
{741, -1186508520}
{742, 164374272}
{743, -17193592248}
{744, -9865437120}
{745, 8106005700}
{746, 2287100532}
{747, -3190649292}
{748, 2475713376}
{749, -731268864}
{750, 262197000}
{751, 11247841832}
{752, 2249189376}
{753, 10656301356}
{754, -1116767880}
{755, 29683680}
{756, -115893504}
{757, 16306837166}
{758, -8901184920}
{759, -391311648}
{760, 4437576000}
{761, 6140694522}
{762, -2719703952}
{763, -257340800}
{764, -5228120064}
{765, 8070423660}
{766, -4571578368}
{767, -6659925240}
{768, 5620278528}
{769, 24506888450}
{770, 141972480}
{771, 3857905098}
{772, -10706680504}
{773, -10172166858}
{774, 2999566728}
{775, -20476871800}
{776, 11651394480}
{777, 464012928}
{778, 9654107940}
{779, 5428169160}
{780, -4938738480}
{781, -5271479136}
{782, -2603791008}
{783, -718626330}
{784, -3159787632}
{785, -12551164860}
{786, -2725937064}
{787, -9791348044}
{788, 10931078808}
{789, -11886499224}
{790, -16178104800}
{791, 1133204352}
{792, 912241440}
{793, -1532774876}
{794, 11280947556}
{795, 4507450740}
{796, 8740978880}
{797, -9757815954}
{798, -89372160}
{799, 16557440256}
{800, 14210301600}
{801, -6217137990}
{802, 1611553932}
{803, -1297889736}
{804, -1259994096}
{805, 381588480}
{806, 8467003104}
{807, -7435923930}
{808, -15822077040}
{809, -2787060150}
{810, 1243571940}
{811, -7999831348}
{812, 214970880}
{813, 11466083736}
{814, -1527375888}
{815, 22753961880}
{816, -2955323232}
{817, -5911354640}
{818, 539687100}
{819, 237852288}
{820, 22594281840}
{821, -10240182138}
{822, -4543274772}
{823, 27868227152}
{824, -9516397440}
{825, 1893464100}
{826, -501649920}
{827, 23512488876}
{828, 1025335584}
{829, -12859810810}
{830, -10241590320}
{831, -13936269402}
{832, -3359622784}
{833, -23260822542}
{834, 1916022600}
{835, -10076236560}
{836, -751801920}
{837, 5448411864}
{838, 10143255960}
{839, -7998323880}
{840, -889574400}
{841, -15916896209}
{842, -6799964748}
{843, 8398156626}
{844, -16490666224}
{845, -14335976070}
{846, 2551336704}
{847, 1189661888}
{848, -1650591648}
{849, 16046324316}
{850, 12599126100}
{851, -4105225488}
{852, 13812609888}
{853, 4208270462}
{854, -115454208}
{855, -2450752200}
{856, -15082420320}
{857, 31930660986}
{858, -782930448}
{859, 21800201180}
{860, -24605499360}
{861, -1088152704}
{862, 13196561472}
{863, 10472788512}
{864, -3781025568}
{865, 24772824180}
{866, -910427028}
{867, -10676510721}
{868, -1629845504}
{869, 6554206560}
{870, -2306701800}
{871, 2585929912}
{872, -5307654000}
{873, -6434747406}
{874, 790695360}
{875, 103584000}
{876, 3400799688}
{877, -17778707194}
{878, 5944575360}
{879, -3118898034}
{880, -1425640320}
{881, -7642529838}
{882, -3584261178}
{883, -27637547308}
{884, 13313488176}
{885, -13756181400}
{886, -10642537368}
{887, 32308710456}
{888, 9570266640}
{889, -1074450944}
{890, -19956245400}
{891, -503806068}
{892, 19001393696}
{893, -5028011520}
{894, -3367110060}
{895, -31572801000}
{896, 1320591360}
{897, -2104332048}
{898, -1662061140}
{899, -10106260080}
{900, -4961355300}
{901, -12150854388}
{902, 3581835984}
{903, 1185014016}
{904, 23372339760}
{905, 25156240980}
{906, -12330144}
{907, 22714240076}
{908, -3992376432}
{909, 8738101638}
{910, 763476480}
{911, 7509250032}
{912, 897445440}
{913, 4149157104}
{914, 17685509916}
{915, -3165970860}
{916, 3329764280}
{917, -1076913408}
{918, -3352329828}
{919, -24937401040}
{920, 7870262400}
{921, 7036194708}
{922, -16601240268}
{923, -28348101936}
{924, 150709248}
{925, 19864210850}
{926, 2781317712}
{927, 5255646768}
{928, 7013424960}
{929, -8662051470}
{930, 17488729440}
{931, 7063633140}
{932, -8485590744}
{933, -15573457224}
{934, -2507530824}
{935, -10494871920}
{936, 4905703440}
{937, 28265471066}
{938, 194781696}
{939, 12422007666}
{940, -20928660480}
{941, -46708171458}
{942, 5213560788}
{943, 9627128784}
{944, 5037401280}
{945, 491287680}
{946, -3900671136}
{947, -46739235324}
{948, -17173680480}
{949, -6979580036}
{950, -3825987000}
{951, -1689015402}
{952, 2398049280}
{953, 38242017882}
{954, -1872325692}
{955, 22162682880}
{956, -4585905600}
{957, 934509960}
{958, -9058373280}
{959, -1794873984}
{960, -6939354240}
{961, 49110054753}
{962, -8213673288}
{963, 8329609404}
{964, -18342408184}
{965, 45387015180}
{966, -158505984}
{967, -49001211184}
{968, 24536776440}
{969, 6606557640}
{970, -20654744760}
{971, 27292866732}
{972, 1320099444}
{973, 756947200}
{974, 5576759616}
{975, 10182362850}
{976, 1159352672}
{977, 3944816706}
{978, -9451645704}
{979, 8084837880}
{980, 29401758360}
{981, 2931272550}
{982, 30768167592}
{983, 474320472}
{984, -22443149520}
{985, -46338268860}
{986, 6218237160}
{987, 1007935488}
{988, -4042917920}
{989, -10484082336}
{990, -1617155280}
{991, 12219675032}
{992, -53173709568}
{993, -18474365844}
{994, -2135282688}
{995, -37054149600}
{996, -10871842032}
{997, -36069016114}
{998, -2463896040}
{999, -5285397258}
{1000, 2136420000}