/*
TASK:str
LANG:C++
*/

#include <stdio.h>

long long ans[1024] = {0,1,1,4,38,728,26704,1866256,1548642,1304331,494115,2286279,3797745,4775141,1852734,2998402,3678438,3259627,4254912,4860978,3466242,917198,2440690,3143911,1353067,2816987,4308823,3000615,2024739,191186,3439964,4726491,2098698,3159083,2386832,3205637,698289,1273727,4405386,66663,1304370,2544752,4187159,2725582,3271286,1737703,3167108,1340296,300146,90521,2891806,2455018,2636665,2945278,1743335,1151180,2844173,2416470,683294,1273853,2796757,4221077,3398929,4123783,3823755,2835026,2242969,4024640,1231894,2820209,3714337,2673124,4055816,3208993,1441045,1773924,1295411,2171534,4787335,4357186,4159420,508163,2195027,361528,2150588,1905776,4019871,1864586,3124197,515012,1258424,3612273,3696667,2640750,2353918,4925352,4929252,3554670,1780172,1064426,2572056,3275966,535571,4719901,2311740,811421,2547168,2999668,2027065,709020,4248687,3027928,4280753,3422346,87343,1662379,597148,775686,3342326,2731111,985434,4206407,737441,100326,1369711,4817966,3870350,2164120,2884504,1356587,4793215,1823263,650166,3118256,2912519,3066549,683169,756997,3818096,1004989,2563826,1056260,1009292,3783204,4631090,3682249,4348362,3858012,64252,3825073,4824268,506391,269292,3831879,3242807,3510685,4302710,3758493,3281613,2940545,777723,3662925,3996379,4826378,2113052,2248078,315006,4749383,2674659,2951466,2822610,1588022,4449218,789904,3639715,2705401,800035,3825096,2454287,3780814,4064381,4369185,4970627,623460,4987815,4002558,841665,2511392,741641,3045982,4236756,231121,3763106,4383416,4238885,3359492,4628418,2482821,733805,4866669,180651,56311,596577,152486,4140342,571979,3822829,110224,938836,3426755,4379382,3928513,2889954,4491279,1859976,3977951,2389383,3411018,4222873,4442459,1690081,4765902,1224691,2167056,3400978,3319865,4450528,1540440,3231262,1382277,3931123,783525,3043451,1120704,2479367,2934328,2750822,394001,4649681,316226,2537993,2816355,4008259,2051406,2703380,4007566,3242293,2799110,4573687,1899080,1472022,2978624,2189141,93904,479918,2246488,260191,702818,1112251,168052,619937,2126927,1764126,865039,2019291,4387721,3238707,1940134,968517,4818826,2643286,3055889,3940911,2795359,1662696,3347487,163026,4297616,4539037,3872705,3476769,4953616,4475101,2290259,2317341,1745953,1404683,847847,3098059,4718232,4955794,4514785,4125223,3004438,3809653,4143584,4134224,1595639,1868115,1926190,3475708,4738880,3293167,3236904,1174410,785650,4451166,2161637,4344778,511180,1788288,2197007,2308266,3520405,1974529,2682479,4491268,8198,4034881,192630,1495425,4936656,2440664,2259067,602681,1861306,3052805,2504895,4630490,3204767,73647,667285,1290402,2431765,1129941,716888,4829371,3516578,1568219,4446701,1123466,4053771,4068343,1981893,4147144,4148076,4399472,664672,2248291,2688966,4047602,3133352,1053732,973575,635934,3819918,2949878,2749796,2068526,1184710,3884592,3645140,1706488,395575,2698388,1370788,600648,177101,2569522,3632720,2612068,4641684,2785717,3451783,4949968,1768950,3943117,4908288,2999238,4588175,4036639,4514230,1126294,4524116,4076944,3103256,4021750,978274,3144113,1356624,129545,463452,817438,3583463,4499444,4649626,1123853,2544928,1835382,4894209,134023,1377038,4263022,3563074,3457167,2608590,3345547,4477516,958855,3248854,3265813,161043,3625823,1562673,4840769,3609202,3749260,3977394,2357312,893601,3803170,4633154,2056896,984764,2712362,1661950,403509,3494394,4177141,95776,4212116,2613251,2511248,4391589,3456989,2424326,4473954,3067499,1609843,1495913,1615241,1826193,3746420,3086979,1854478,2127585,2486558,414773,1988139,4818976,2160869,2735410,2663690,2331154,4638114,114803,1094443,365482,4249890,2820633,1449061,1584533,1164725,4093429,2930385,3534340,3032181,2453507,1975578,1830450,4519732,909528,1434509,4833870,1334498,2720230,3885782,2815638,3986877,35759,2228726,3212896,964257,1905373,2911210,4097649,1920122,2487954,2179121,4093801,2168383,256845,593267,1758387,479418,3300823,854893,3251367,26655,3401440,99783,857842,1619663,234727,1107336,2139753,3159694,51263,4274151,248569,1541488,514093,751860,3216318,2940290,2174287,1176108,4694130,125200,4644258,4952040,1369856,853997,3347658,3475173,4149724,4173140,561013,2321588,1872253,3755446,1245150,3487523,3235033,4073038,3927721,4127207,400228,4171915,2198535,49105,3534941,240634,4170794,2867181,1453740,1073763,3777929,3284708,2956934,3841389,3589249,1594582,2278597,4873890,1610039,3636129,724698,1862861,2932855,3095644,4767228,3584281,3531568,999437,3410520,137104,3457934,1765515,4997759,2408874,264626,3207046,3378628,2366118,3710222,2609618,440990,4741354,1408535,4756408,24997,3284272,1422104,4630480,892311,2302153,1099019,1709832,3657369,2305297,1461195,688258,3996163,4772427,626627,1161045,1045098,2461181,3989539,3532766,3193000,4912955,881646,4886538,4646692,770574,733565,4065255,3181767,3021967,1920,3971332,2913209,451854,3774893,2417664,2184618,4908874,821385,2232052,4060922,4517990,421646,2920754,519343,2930525,1971605,2895981,4533027,2050669,2100499,1564171,840496,3524249,843895,2341210,2370283,4584040,1808315,690353,2749050,253159,3119004,4560424,2543229,26397,702483,1448878,206640,3876414,1704231,1563915,4701595,2931019,1405269,2772005,1104048,127017,1903708,829405,3073748,2164034,1949411,748367,4793544,3258560,530868,3848702,2610452,4458136,1166170,2648708,4489982,690141,3079077,920933,1785665,2010078,326212,2733839,4122547,3180425,4791880,1642366,4418452,563282,4597450,549114,125136,4245775,3033084,2973666,2523739,4997491,1794582,50396,3630348,1099606,2116093,4359263,152915,2274861,2876887,4839898,3703852,4986125,338789,4189687,3840352,900142,4131982,286122,2440158,286012,677499,1928968,3208397,1184919,3849412,3998371,1341182,1208489,997861,3419087,3933348,3835593,1865639,2091449,33773,4967542,4232832,1812774,4564448,2697591,725804,885121,1991594,1479521,3756612,2827366,4327194,419807,3676172,3275131,3985659,2451526,3002904,1798307,2646598,1251381,3485590,4364529,1256467,880108,2083282,1124464,2241879,2042109,2784696,1543941,2697353,2145907,2770109,3732335,34737,4834321,4618149,4877325,1918909,3447189,3641826,1659044,1548420,1089037,3803272,1731425,4345523,440041,4831531,385043,657754,3346023,1765136,3726887,4283481,4793911,1123869,3723605,861227,4316741,3680219,2014193,2844041,1766741,1293985,860923,2889278,1364469,1105194,771771,2794574,2508864,466249,3222288,2439671,1156733,2369731,1626249,2247155,3791051,2769471,1017546,2991915,4358620,2637258,1485676,387331,2517805,1422890,1032565,4127662,4611476,1253459,3798683,2004445,4568936,1891488,761197,2079076,4045888,479417,1263105,4766114,1441684,4432275,4249002,2461050,944019,2190720,186836,3660670,3775242,760345,2000358,2268500,2034887,2435079,3189586,2729233,4514207,2643449,1786453,1569684,1454792,311553,3057524,1871825,1254118,638716,556825,2780057,3192582,3728774,3920497,4700745,33062,4864488,86920,3263299,4989549,1754092,4968922,1775639,2803411,1804265,102409,2728118,1512267,2158072,3164855,402191,4876704,712734,4661152,3764651,4889013,442725,4556719,3668509,2591913,543980,3649376,4737822,3471211,4002494,4225887,1802929,2433415,716391,1667560,3117553,994915,590664,4740521,2388658,2643333,2714412,4065143,3094431,4903201,1736126,1754548,4062181,1838924,1994926,1749508,2494823,3378753,4576373,1201007,16439,4947937,1118185,2439085,4451932,1911985,1590134,207677,4263061,4987335,1104879,3676554,1607552,1389229,3278212,513480,1626937,4199855,4216917,1824042,3123107,1470604,1640095,1480189,1423393,3851592,4877024,4296393,3009296,2529903,3812807,4580601,3678430,465626,2832152,4411848,4838640,2157812,2323065,3409626,1267645,4166980,2570639,1402302,694070,1102659,637713,1895292,1126159,3814107,582068,1926621,190506,844321,484762,922753,3896267,4381622,1007910,576234,2228849,1306834,793647,3588778,3423878,225172,4798558,1458847,4051780,2134259,2578243,860515,3221282,4018299,4499897,1760826,1740822,2286022,515918,898597};

int main () {

    int N;
    scanf("%d",&N);
    printf("%lld\n",ans[N]);
    return 0;
}
