{1, 1}
{2, 16}
{3, -156}
{4, 256}
{5, 870}
{6, -2496}
{7, -952}
{8, 4096}
{9, 4653}
{10, 13920}
{11, -56148}
{12, -39936}
{13, 178094}
{14, -15232}
{15, -135720}
{16, 65536}
{17, -247662}
{18, 74448}
{19, 315380}
{20, 222720}
{21, 148512}
{22, -898368}
{23, 204504}
{24, -638976}
{25, -1196225}
{26, 2849504}
{27, 2344680}
{28, -243712}
{29, -3840450}
{30, -2171520}
{31, -1309408}
{32, 1048576}
{33, 8759088}
{34, -3962592}
{35, -828240}
{36, 1191168}
{37, 4307078}
{38, 5046080}
{39, -27782664}
{40, 3563520}
{41, 1512042}
{42, 2376192}
{43, 33670604}
{44, -14373888}
{45, 4048110}
{46, 3272064}
{47, -10581072}
{48, -10223616}
{49, -39447303}
{50, -19139600}
{51, 38635272}
{52, 45592064}
{53, 16616214}
{54, 37514880}
{55, -48848760}
{56, -3899392}
{57, -49199280}
{58, -61447200}
{59, 112235100}
{60, -34744320}
{61, -33197218}
{62, -20950528}
{63, -4429656}
{64, 16777216}
{65, 154941780}
{66, 140145408}
{67, -121372252}
{68, -63401472}
{69, -31902624}
{70, -13251840}
{71, -387172728}
{72, 19058688}
{73, 255240074}
{74, 68913248}
{75, 186611100}
{76, 80737280}
{77, 53452896}
{78, -444522624}
{79, 492101840}
{80, 57016320}
{81, -457355079}
{82, 24192672}
{83, -457420236}
{84, 38019072}
{85, -215465940}
{86, 538729664}
{87, 599110200}
{88, -229982208}
{89, -31809510}
{90, 64769760}
{91, -169545488}
{92, 52353024}
{93, 204267648}
{94, -169297152}
{95, 274380600}
{96, -163577856}
{97, -673532062}
{98, -631156848}
{99, -261256644}
{100, -306233600}
{101, 1057718982}
{102, 618164352}
{103, 795866024}
{104, 729473024}
{105, 129205440}
{106, 265859424}
{107, -1974134772}
{108, 600238080}
{109, -1344647410}
{110, -781580160}
{111, -671904168}
{112, -62390272}
{113, 2706802674}
{114, -787188480}
{115, 177918480}
{116, -983155200}
{117, 828671382}
{118, 1795761600}
{119, 235774224}
{120, -555909120}
{121, 794650213}
{122, -531155488}
{123, -235878552}
{124, -335208448}
{125, -2739934500}
{126, -70874496}
{127, 1199600768}
{128, 268435456}
{129, -5252614224}
{130, 2479068480}
{131, 2786145252}
{132, 2242326528}
{133, -300241760}
{134, -1941956032}
{135, 2039871600}
{136, -1014423552}
{137, 2882330058}
{138, -510441984}
{139, 2156411180}
{140, -212029440}
{141, 1650647232}
{142, -6194763648}
{143, -9999621912}
{144, 304939008}
{145, -3341191500}
{146, 4083841184}
{147, 6153779268}
{148, 1102611968}
{149, 7545477750}
{150, 2985777600}
{151, -4313083048}
{152, 1291796480}
{153, -1152371286}
{154, 855246336}
{155, -1139184960}
{156, -7112361984}
{157, -4231572802}
{158, 7873629440}
{159, -2592129384}
{160, 912261120}
{161, -194687808}
{162, -7317681264}
{163, 828448004}
{164, 387082752}
{165, 7620406560}
{166, -7318723776}
{167, -2854998552}
{168, 608305152}
{169, 21112973463}
{170, -3447455040}
{171, 1467463140}
{172, 8619674624}
{173, -17669017266}
{174, 9585763200}
{175, 1138806200}
{176, -3679715328}
{177, -17508675600}
{178, -508952160}
{179, -586732140}
{180, 1036316160}
{181, -5433956458}
{182, -2712727808}
{183, 5178766008}
{184, 837648384}
{185, 3747157860}
{186, 3268282368}
{187, 13905725976}
{188, -2708754432}
{189, -2232135360}
{190, 4390089600}
{191, 32329244352}
{192, -2617245696}
{193, -12939916606}
{194, -10776512992}
{195, -24170917680}
{196, -10098509568}
{197, 8810897958}
{198, -4180106304}
{199, -24853394680}
{200, -4899737600}
{201, 18934071312}
{202, 16923503712}
{203, 3656108400}
{204, 9890629632}
{205, 1315476540}
{206, 12733856384}
{207, 951557112}
{208, 11671568384}
{209, -17707956240}
{210, 2067287040}
{211, -46516300108}
{212, 4253750784}
{213, 60398945568}
{214, -31586156352}
{215, 29293425480}
{216, 9603809280}
{217, 1246556416}
{218, -21514358560}
{219, -39817451544}
{220, -12505282560}
{221, -44107116228}
{222, -10750466688}
{223, 46634730464}
{224, -998244352}
{225, -5566034925}
{226, 43308842784}
{227, 26586730308}
{228, -12595015680}
{229, 39990726470}
{230, 2846695680}
{231, -8338651776}
{232, -15730483200}
{233, 6533375274}
{234, 13258742112}
{235, -9205532640}
{236, 28732185600}
{237, -76767887040}
{238, 3772387584}
{239, -56677299600}
{240, -8894545920}
{241, 4614914162}
{242, 12714403408}
{243, 25197055884}
{244, -8498487808}
{245, -34319153610}
{246, -3774056832}
{247, 56167285720}
{248, -5363335168}
{249, 71357556816}
{250, -43838952000}
{251, 68019386652}
{252, -1133991936}
{253, -11482490592}
{254, 19193612288}
{255, 33612686640}
{256, 4294967296}
{257, -93595760382}
{258, -84041827584}
{259, -4100338256}
{260, 39665095680}
{261, -17869613850}
{262, 44578324032}
{263, -94040095416}
{264, 35877224448}
{265, 14456106180}
{266, -4803868160}
{267, 4962283560}
{268, -31071296512}
{269, 122724427950}
{270, 32637945600}
{271, -164257407088}
{272, -16230776832}
{273, 26449096128}
{274, 46117280928}
{275, 67165641300}
{276, -8167071744}
{277, 65013397238}
{278, 34502578880}
{279, -6092675424}
{280, -3392471040}
{281, 52096444122}
{282, 26410355712}
{283, -90699183556}
{284, -99116218368}
{285, -42803373600}
{286, -159993950592}
{287, -1439463984}
{288, 4879024128}
{289, -57251410253}
{290, -53459064000}
{291, 105071001672}
{292, 65341458944}
{293, 72556898694}
{294, 98460468288}
{295, 97644537000}
{296, 17641791488}
{297, -131649092640}
{298, 120727644000}
{299, 36420935376}
{300, 47772441600}
{301, -32054415008}
{302, -69009328768}
{303, -165004161192}
{304, 20668743680}
{305, -28881579660}
{306, -18437940576}
{307, 181977113108}
{308, 13683941376}
{309, -124155099744}
{310, -18226959360}
{311, -89829518088}
{312, -113797791744}
{313, 5513937914}
{314, -67705164832}
{315, -3853800720}
{316, 125978071040}
{317, -19480554402}
{318, -41474070144}
{319, 215633586600}
{320, 14596177920}
{321, 307965024432}
{322, -3115004928}
{323, -78107641560}
{324, -117082900224}
{325, -213040495150}
{326, 13255168064}
{327, 209764995960}
{328, 6193324032}
{329, 10073180544}
{330, 121926504960}
{331, -106801000468}
{332, -117099580416}
{333, 20040833934}
{334, -45679976832}
{335, -105593859240}
{336, 9732882432}
{337, -175776423982}
{338, 337807575408}
{339, -422261217144}
{340, -55159280640}
{341, 73520640384}
{342, 23479410240}
{343, 75970466320}
{344, 137914793984}
{345, -27755282880}
{346, -282704276256}
{347, 83302636668}
{348, 153372211200}
{349, 321367902590}
{350, 18220899200}
{351, 417573439920}
{352, -58875445248}
{353, 407688457314}
{354, -280138809600}
{355, -336840273360}
{356, -8143234560}
{357, -36780778944}
{358, -9387714240}
{359, -560078988120}
{360, 16581058560}
{361, -223223153379}
{362, -86943303328}
{363, -123965433228}
{364, -43403644928}
{365, 222058864380}
{366, 82860256128}
{367, 376056463088}
{368, 13402374144}
{369, 7035531426}
{370, 59954525760}
{371, -15818635728}
{372, 52292517888}
{373, -81224458666}
{374, 222491615616}
{375, 427429782000}
{376, -43340070912}
{377, -683961102300}
{378, -35714165760}
{379, 202729151900}
{380, 70241433600}
{381, -187137719808}
{382, 517267909632}
{383, -47681602176}
{384, -41875931136}
{385, 46504019520}
{386, -207038665696}
{387, 156669320412}
{388, -172424207872}
{389, -189794662170}
{390, -386734682880}
{391, -50647869648}
{392, -161576153088}
{393, -434638659312}
{394, 140974367328}
{395, 428128600800}
{396, -66881700864}
{397, 400237219118}
{398, -397654314880}
{399, 46837714560}
{400, -78395801600}
{401, 876185839122}
{402, 302945140992}
{403, -233197708352}
{404, 270776059392}
{405, -397898918730}
{406, 58497734400}
{407, -241833815544}
{408, 158250074112}
{409, 572299984730}
{410, 21047624640}
{411, -449643489048}
{412, 203741702144}
{413, -106847815200}
{414, 15224913792}
{415, -397955605320}
{416, 186745094144}
{417, -336400144080}
{418, -283327299840}
{419, 416692614660}
{420, 33076592640}
{421, -1190433985018}
{422, -744260801728}
{423, -49233728016}
{424, 68060012544}
{425, 296259475950}
{426, 966383129088}
{427, 31603751536}
{428, -505378501632}
{429, 1559941018272}
{430, 468694807680}
{431, -436455134928}
{432, 153660948480}
{433, 448430049074}
{434, 19944902656}
{435, 521225874000}
{436, -344229736960}
{437, 64496471520}
{438, -637079224704}
{439, -659702920840}
{440, -200084520960}
{441, -183548300859}
{442, -705713859648}
{443, 948506603484}
{444, -172007467008}
{445, -27674273700}
{446, 746155687424}
{447, -1177094529000}
{448, -15971909632}
{449, -611762940990}
{450, -89056558800}
{451, -84898134216}
{452, 692941484544}
{453, 672840955488}
{454, 425387684928}
{455, -147504574560}
{456, -201520250880}
{457, -379032618742}
{458, 639851623520}
{459, -580688138160}
{460, 45547130880}
{461, -890062477458}
{462, -133418428416}
{463, 1328521649744}
{464, -251687731200}
{465, 177712853760}
{466, 104534004384}
{467, 1656376397748}
{468, 212139873792}
{469, 115546383904}
{470, -147288522240}
{471, 660125357112}
{472, 459714969600}
{473, -1890537073392}
{474, -1228286192640}
{475, -377265440500}
{476, 60358201344}
{477, 77315243742}
{478, -906836793600}
{479, -1079731180320}
{480, -142312734720}
{481, 767064749332}
{482, 73838626592}
{483, 30371298048}
{484, 203430454528}
{485, -585972893940}
{486, 403152894144}
{487, 1605486047528}
{488, -135975804928}
{489, -129237888624}
{490, -549106457760}
{491, 793629275532}
{492, -60384909312}
{493, 951133527900}
{494, 898676571520}
{495, -227293280280}
{496, -85813362688}
{497, 368588437056}
{498, 1141720909056}
{499, -1969508923180}
{500, -701423232000}
{501, 445379774112}
{502, 1088310186432}
{503, -542230355016}
{504, -18143870976}
{505, 920215514340}
{506, -183719849472}
{507, -3293623860228}
{508, 307097796608}
{509, -1692147528930}
{510, 537802986240}
{511, -242988550448}
{512, 68719476736}
{513, 739465178400}
{514, -1497532166112}
{515, 692403440880}
{516, -1344669241344}
{517, 594106030656}
{518, -65605412096}
{519, 2756366693496}
{520, 634641530880}
{521, 2975959460682}
{522, -285913821600}
{523, -1079894255956}
{524, 713253184512}
{525, -177653767200}
{526, -1504641526656}
{527, 324290604096}
{528, 574035591168}
{529, -1759330775447}
{530, 231297698880}
{531, 522229920300}
{532, -76861890560}
{533, 269285607948}
{534, 79396536960}
{535, -1717497251640}
{536, -497140744192}
{537, 91530213840}
{538, 1963590847200}
{539, 2214887168844}
{540, 522207129600}
{541, -2021673615298}
{542, -2628118513408}
{543, 847697207448}
{544, -259692429312}
{545, -1169843246700}
{546, 423185538048}
{547, -2626119837052}
{548, 737876494848}
{549, -154466655354}
{550, 1074650260800}
{551, -1211201121000}
{552, -130673147904}
{553, -468480951680}
{554, 1040214355808}
{555, -584556626160}
{556, 552041262080}
{557, 3484820127438}
{558, -97482806784}
{559, 5996532548776}
{560, -54279536640}
{561, -2169293252256}
{562, 833543105952}
{563, -2770913613036}
{564, 422565691392}
{565, 2354918326380}
{566, -1451186936896}
{567, 435402035208}
{568, -1585859493888}
{569, -670382371590}
{570, -684853977600}
{571, 2671233315932}
{572, -2559903209472}
{573, -5043362118912}
{574, -23031423744}
{575, -244632797400}
{576, 78064386048}
{577, -659284138942}
{578, -916022564048}
{579, 2018626990536}
{580, -855345024000}
{581, 435464064672}
{582, 1681136026752}
{583, -932967183672}
{584, 1045463343104}
{585, 720944102340}
{586, 1160910379104}
{587, 1049465239788}
{588, 1575367492608}
{589, -412961095040}
{590, 1562312592000}
{591, -1374500081448}
{592, 282268663808}
{593, -1311883953966}
{594, -2106385482240}
{595, 205123574880}
{596, 1931642304000}
{597, 3877129570080}
{598, 582734966016}
{599, -3376028300520}
{600, 764359065600}
{601, 2638803841562}
{602, -512870640128}
{603, -564745088556}
{604, -1104149260288}
{605, 691345685310}
{606, -2640066579072}
{607, -5159389404832}
{608, 330699898880}
{609, -570352910400}
{610, -462105274560}
{611, -1884425436768}
{612, -295007049216}
{613, -537353626426}
{614, 2911633809728}
{615, -205214340240}
{616, 218943062016}
{617, 4633581879978}
{618, -1986481595904}
{619, 3062671313420}
{620, -291631349760}
{621, 479496438720}
{622, -1437272289408}
{623, 30282653520}
{624, -1820764667904}
{625, -47366061875}
{626, 88223006624}
{627, 2762441173440}
{628, -1083282637312}
{629, -1066699551636}
{630, -61660811520}
{631, -54692849608}
{632, 2015649136640}
{633, 7256542816848}
{634, -311688870432}
{635, 1043652668160}
{636, -663585122304}
{637, -7025327980482}
{638, 3450137385600}
{639, -1801514703384}
{640, 233538846720}
{641, -4780679546238}
{642, 4927440390912}
{643, 4104842552804}
{644, -49840078848}
{645, -4569774374880}
{646, -1249722264960}
{647, -5492629724472}
{648, -1873326403584}
{649, -6301776394800}
{650, -3408647922400}
{651, -194462800896}
{652, 212082689024}
{653, 4159943034414}
{654, 3356239935360}
{655, 2423946369240}
{656, 99093184512}
{657, 1187632064322}
{658, 161170888704}
{659, 2152945882740}
{660, 1950824079360}
{661, 8639782534262}
{662, -1708816007488}
{663, 6880710131568}
{664, -1873593286656}
{665, -261210331200}
{666, 320653342944}
{667, -785387386800}
{668, -730879629312}
{669, -7275017952384}
{670, -1689501747840}
{671, 1863957396264}
{672, 155726118912}
{673, -2907884393566}
{674, -2812422783712}
{675, -2804764833000}
{676, 5404921206528}
{677, 4268219834118}
{678, -6756179474304}
{679, 641202523024}
{680, -882548490240}
{681, -4147529928048}
{682, 1176330246144}
{683, -769165099956}
{684, 375670563840}
{685, 2507627150460}
{686, 1215527461120}
{687, -6238553329320}
{688, 2206636703744}
{689, 2959248016116}
{690, -444084526080}
{691, 1386484613012}
{692, -4523268420096}
{693, 248716325088}
{694, 1332842186688}
{695, 1876077726600}
{696, 2453955379200}
{697, -374475345804}
{698, 5141886441440}
{699, -1019206542744}
{700, 291534387200}
{701, -5511859848738}
{702, 6681175038720}
{703, 1358366259640}
{704, -942007123968}
{705, 1436063091840}
{706, 6523015317024}
{707, -1006948470864}
{708, -4482220953600}
{709, 2431522040870}
{710, -5389444373760}
{711, 2289749861520}
{712, -130291752960}
{713, -267779173632}
{714, -588492463104}
{715, -8699671063440}
{716, -150203427840}
{717, 8841658737600}
{718, -8961263809920}
{719, -2708898248880}
{720, 265296936960}
{721, -757664454848}
{722, -3571570454064}
{723, -719926609272}
{724, -1391092853248}
{725, 4594042301250}
{726, -1983446931648}
{727, 526646689688}
{728, -694458318848}
{729, 5071379302053}
{730, 3552941830080}
{731, -8338929127848}
{732, 1325764098048}
{733, -2780092868866}
{734, 6016903409408}
{735, 5353787963160}
{736, 214437986304}
{737, 6814809205296}
{738, 112568502816}
{739, -2365576289980}
{740, 959272412160}
{741, -8762096572320}
{742, -253098171648}
{743, 13139774626344}
{744, 836680286208}
{745, 6564565642500}
{746, -1299591338656}
{747, -2128376358108}
{748, 3559865849856}
{749, 1879376302944}
{750, 6838876512000}
{751, -7294364410768}
{752, -693441134592}
{753, -10611024317712}
{754, -10943377636800}
{755, -3752382251760}
{756, -571426652160}
{757, -16301969136682}
{758, 3243666430400}
{759, 1791268532352}
{760, 1123862937600}
{761, -9689446243398}
{762, -2994203516928}
{763, 1280104334320}
{764, 8276286554112}
{765, -1002563018820}
{766, -762905634816}
{767, 19988397899400}
{768, -670014898176}
{769, 12132873232130}
{770, 744064312320}
{771, 14600938619592}
{772, -3312618651136}
{773, -16864650951066}
{774, 2506709126592}
{775, 1566346584800}
{776, -2758787325952}
{777, 639652767936}
{778, -3036714594720}
{779, 476867805960}
{780, -6187754926080}
{781, 21738974331744}
{782, -810365914368}
{783, -9004626306000}
{784, -2585218449408}
{785, -3681468337740}
{786, -6954218548992}
{787, -6001159578892}
{788, 2255589877248}
{789, 14670254884896}
{790, 6850057612800}
{791, -2576876145648}
{792, -1070107213824}
{793, -5912225342492}
{794, 6403795505888}
{795, -2255152564080}
{796, -6362469038080}
{797, -14315504363202}
{798, 749403432960}
{799, 2620529453664}
{800, -1254332825600}
{801, -148009650030}
{802, 14018973425952}
{803, -14331219674952}
{804, 4847122255872}
{805, -169378392960}
{806, -3731163333632}
{807, -19145010760200}
{808, 4332416950272}
{809, -10989330977430}
{810, -6366382699680}
{811, 21544361627852}
{812, 935963750400}
{813, 25624155505728}
{814, -3869341048704}
{815, 720749763480}
{816, 2532001185792}
{817, 10619035089520}
{818, 9156799755680}
{819, -788895155664}
{820, 336761994240}
{821, 5717478970902}
{822, -7194295824768}
{823, -10052437891336}
{824, 3259867234304}
{825, -10477840042800}
{826, -1709565043200}
{827, 22958121262428}
{828, 243598620672}
{829, -15727726682530}
{830, -6367289685120}
{831, -10142089969128}
{832, 2987921506304}
{833, 9769597955586}
{834, -5382402305280}
{835, -2483848740240}
{836, -4533236797440}
{837, -3070142749440}
{838, 6667081834560}
{839, -8521678548600}
{840, 529225482240}
{841, 241910226631}
{842, -19046943760288}
{843, -8127045283032}
{844, -11908172827648}
{845, 18368286912810}
{846, -787739648256}
{847, -756507002776}
{848, 1088960200704}
{849, 14149072634736}
{850, 4740151615200}
{851, 880814679312}
{852, 15462130065408}
{853, -1831603068106}
{854, 505660024576}
{855, 1276692931800}
{856, -8086056026112}
{857, -620072354022}
{858, 24959056292352}
{859, -5715810374020}
{860, 7499116922880}
{861, 224556381504}
{862, -6983282158848}
{863, 20259551636064}
{864, 2458575175680}
{865, -15372045021420}
{866, 7174880785184}
{867, 8931219999468}
{868, 319118442496}
{869, -27630534112320}
{870, 8339613984000}
{871, -21615669847688}
{872, -5507675791360}
{873, -3133944684486}
{874, 1031943544320}
{875, 2608417644000}
{876, -10193267595264}
{877, -91457250802}
{878, -10555246733440}
{879, -11318876196264}
{880, -3201352335360}
{881, 17315004551922}
{882, -2936772813744}
{883, 13878128084564}
{884, -11291421754368}
{885, -15232547772000}
{886, 15176105655744}
{887, 17658551034168}
{888, -2752119472128}
{889, -1142019931136}
{890, -442788379200}
{891, 25679572975692}
{892, 11938490998784}
{893, -3337058487360}
{894, -18833512464000}
{895, -510456961800}
{896, -255550554112}
{897, -5681665918656}
{898, -9788207055840}
{899, 5028715953600}
{900, -1424904940800}
{901, -4115204791668}
{902, -1358370147456}
{903, 5000488741248}
{904, 11087063752704}
{905, -4727542118460}
{906, 10765455287808}
{907, 12392374416428}
{908, 6806202958848}
{909, 4921566423246}
{910, -2360073192960}
{911, -13810380634608}
{912, -3224324014080}
{913, 25683231410928}
{914, -6064521899872}
{915, 4505526426960}
{916, 10237625976320}
{917, -2652410279904}
{918, -9291010210560}
{919, 856606346840}
{920, 728754094080}
{921, -28388429644848}
{922, -14240999639328}
{923, -68953139820432}
{924, -2134694854656}
{925, -5152234380550}
{926, 21256346395904}
{927, 3703164609672}
{928, -4027003699200}
{929, 12916914336930}
{930, 2843405660160}
{931, -12440890420140}
{932, 1672544070144}
{933, 14013404821728}
{934, 26502022363968}
{935, 12097981599120}
{936, 3394237980672}
{937, -3678673359382}
{938, 1848742142464}
{939, -860174314584}
{940, -2356616355840}
{941, 44514500834382}
{942, 10562005713792}
{943, 309218637168}
{944, 7355439513600}
{945, -1941957763200}
{946, -30248593174272}
{947, -19954325186412}
{948, -19652579082240}
{949, 45456725738956}
{950, -6036247048000}
{951, 3038966486712}
{952, 965731221504}
{953, 7132015155834}
{954, 1237043899872}
{955, 28126442586240}
{956, -14509388697600}
{957, -33638839509600}
{958, -17275698885120}
{959, -2743978215216}
{960, -2277003755520}
{961, -24725072850207}
{962, 12273035989312}
{963, -9185649094116}
{964, 1181418025472}
{965, -11257727447220}
{966, 485940768768}
{967, 2841758123528}
{968, 3254887272448}
{969, 12184792083360}
{970, -9375566303040}
{971, -39030869592468}
{972, 6450446306304}
{973, -2052903443360}
{974, 25687776760448}
{975, 33234317243400}
{976, -2175612878848}
{977, -21755586348462}
{978, -2067806217984}
{979, 1786040367480}
{980, -8785703324160}
{981, -6256644398730}
{982, 12698068408512}
{983, 46499831376024}
{984, -966158548992}
{985, 7665481223460}
{986, 15218136446400}
{987, -1571416164864}
{988, 14378825144320}
{989, 6885773200416}
{990, -3636692484480}
{991, -15520906240288}
{992, -1373013803008}
{993, 16660956073008}
{994, 5897414992896}
{995, -21622453371600}
{996, 18267534544896}
{997, -42633356836282}
{998, -31512142770880}
{999, 10098719645040}
{1000, -11222771712000}