#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> l = {24,56,132,312,736,1736,4096,9664,22800,53792,126912,299424,706432,1666688,3932224,9277312,1677892,11220232,574872,4505528,11241412,3422460,15855976,13774560,14183932,19659600,6237996,423640,19956372,11968520,4574212,8640952,798728,10745880,18563556,18514460,18100464,12697716,1794028,19578876,3922860,11433776,1394980,10635680,3718696,10227352,1305848,10049088,132664,2877024,5642116,11549560,8643060,8360244,19609500,16084904,8470080,15738944,3017372,2764796,16797372,19419380,3948136,1070800,560144,9016560,20174720,1049512,20132144,19983404,1645616,3135304,5817200,14925632,15911764,3037712,15716580,2626364,11328152,13669248,12381116,6998320,914920,6381964,6550460,14930760,2205232,17511384,4253964,12918392,229228,8966384,3349336,7157128,12036916,10562396,15228940,14111496,8927568,7892800,3588376,4821780,5219052,17614856,4453056,19344216,13287820,15271644,8601396,3358216,17049612,10881800,8269924,10218856,1781096,20102040,11468,3585128,6954120,13931176,14822500,3133024,13918292,17061368,20178676,7563612,8829744,17596624,9900256,17249892,9062708,17715820,9301100,16517508,7836332,14064756,534204,16741072,981332,3031072,19334180,210808,6483760,11215664,2642836,18253192,18517496,1900448,20097172,16599012,16788812,13141644,19061096,11069492,8002056,13706088,9130944,14055892,15103744,8049160,3789888,17577156,10832416,9034500,12803096,6850808,11560508,8306992,10105492,2911784,2227444,4455764,14735096,13714972,16131364,1102596,9425028,10692568,3380220,5400388,11975804,10501940,11594548,6720488,14234748,11238376,15707620,19464520,775468,12756068,3810852,9172640,3437200,14496104,6917272,498836,9779772,13183980,7155524,13660484,13268712,428256,7967372,2051952,4960416,5645468,15394840,290296,11871528,14112520,8595524,513888,9042708,15066356,10950380,19776068,9054524,19799700,18521212,14731256,8431588,13485384,16013064,8469088,3488728,18793476,14104912,14977172,6910972,1611552,12967340,19546516,1895920,9516412,17705640,18993012,16598632,7978220,13522248,19821544,15179312,16982904,12978572,15895552,5126588,16000212,3161204,16575584,4521268,15364944,3250732,15544000,1187564,8876592,8420968,19217064,15767096,7955912,13925736,18965448,13422504,14276264,5853100,18341100,4604404,704900,17881892,4552376,10514552,16372672,1429880,3678756,19892748,2225040,11807592,2770356,9990792,3176552,11893816,3349000,13051104,9469624,5427140,16746380,12011792,14667756,2197948,8209372,5334040,15063976,6126480,2710932,15339708,2512160,10446184,11151568,7117348,14916956,11716832,17458252,4120092,11463740,17423768,2667504,8052380,10532080,6189060,8272772,17399596,6757096,9849628,14078232,1250440,1990028,11926412,6143596,16267248,15967104,3801184,19926756,11157396,9707052,18847400,19589376,18172640,13409756,5367940,6660944,19931292,10178248,13468276,6168812,12484012,11484360,15096236,14740280,12029064,13830384,16721112,17080136,1190716,15613548,4757044,11895520,14597920,18499820,160356,9306444,15192312,10495228,19393236,8540772,17861892,13879932,4421192,4145952,15841660,105488,8502880,8268864,16748704,10082952,16493524,5854132,11664060,15894952,3077952,9273916,9917520,5780836,9899396,19423724,9988904,19566492,17350108,14257808,7018276,8316552,4728504,3283452,2989900,15436808,17230412,20408,10704324,15449256,10729220,2446872,15582148,12202520,9088676,8921432,1827688,1622620,877996,5411368,14067976,9681836,9976300,7668336,14490236,8512856,12152276,12864808,2335112,8764668,2838736,10347696,18014620,1286496,3058276,1725576,6024144,18164840,19570724,10769520,17448504,13408132,7935088,10346968,7089984,9840036,20163900,14087552,7434960,14777504,17309896,9069496,7273784,8747144,15423172,4973696,7231572,4889272,19725936,13494800,16558036,11937620,10444624,13585104,10625232,1719496,10399092,1628432,6695856,13979788,11006332,15194268,17927896,17448240,4654692,4744960,3966184,17241752,3553208,15038784,3930748,14967912,19593176,6627632,2770872,4307880,1660916,8863576,6132804,15587440,8481816,9019132,8792928,14339380,6296808,9969364,8197272,8778052,17284724,10543776,18433548,10806220,2279776,1006432,3415196,11389944,4582644,15995680,14351032,17657244,6675524,1632896,18370172,9671176,2398036,1116200,1364644,7525360,17283120,17085420,8801344,11748712,17248048,11678568,6434344,6944568,17036164,6520800,6720628,7093368,7018228,7267604,8511836,10850020,16025140,8653736,18797404,9014764,15126892,7218268,12255956,14345480,2707280,9716364,7703472,611396,445412,16297768,13608220,7897156,7969632,2735488,1055180,18049624,1150008,4410376,4499784,11299584,11209812,11209084,4597120,11403756,4805464,18805168,19997632,9185976,15562072,10489084,19140012,8773844,18315748,14281196,5689864,7591008,3324192,18028112,10818024,8074324,11784656,4785144,5508828,14376860,18113900,6825240,1983984,19985660,13201584,10161028,19873160,5519164,11150276,1416548,13871424,9623184,1869356,11271452,1369056,6476824,15286444,13100892,18945324,7833212,1447992,366416,16399256,15484388,11491500,15361296,1061044,4894980,92336,2306760,14403480,8781524,1966460,12529772,2202376,8337672,1314672,7034096,10533428,3486092,830268,2517284,12006752,5463932,15962432,15518152,1543952,14802660,11300,3110504,15616220,11044932,8100764,7013752,15907260,7595832,9009060,9412424,13806404,5210712,9036164,5264920,741156,19554640,9218904,19920120,18319196,14655984,8521884,13261944,15415640,7454832,1013336,12647844,19995244,1596944,8279468,16129208,15242196,6623112,5084424,233024,13712272,17383284,15022508,17049344,8234932,6094664,5867800,7995356,7969932,7465356,10711316,17152388,8815272,18843068,11360588,20141612,17339036,16979032,13610964,1269676,16287308,19376328,871792,14108092,6338516,14420616,16637200,5531216,19693556,12031188,14914700,8586188,814536,11248364,19458996,126848,2540316,3578408,7410512,19901656,6539912,7690740,14764576,2188760,19759000,8416828,1001068,1099920,19033496,19859020,1497664,642104,582032,4159392,9602992,159940,8638664,16273204,12656180,2169472,16675244,18242632,403992,13948364,3751668,8311320,4099152,15701640,7605704,3199604,17592380,9975952,6141004,7046552,13834900,19741700,13156288,13562160,5977396,18057260,2608516,17171824,9827844,4662612,3248656,5942892,1000900,8499112,8673900,19349600,15277208,7482000,13242984,16620168,7784120,1633992,16298212,7744448,18756880,9479860,14238508,5360452,9470516,6997832,4506460,7743844,9273244,7349300,9976180,18288740,10855864,1243872,18855116,19001744,71016,17642156,12657476,5246876,5357848,15820540,1714616,14144928,19510720,2030456,12140660,2672436,9405784,2672672,10690216,19981892,4888912,10948148,1229756,12237336,5950752,14361016,12776488,17244372,2580452,10503772,15076072,15102940,10793208,11318344,12422352,6010904,14448388,13321264,18454228,5174908,16782236,9842604,9824916,12794088,4853168,9146060,3460080,16626496,11124896,8959844,10752464,3334504,4378588,10051996,6562892,1672852,3239588,19604960,2135408,10749992,79580,4429976,10149828,248708,9357368,18804284,17895876,14086272,5150788,5673112,19308660,8498680,8133476,14464056,5505256,7067356,2642608,16295728,6305952,17897120,7755372,7912540,11199104,17698844,10802552,3583096,2143664,5682324,18530840,928792,13222232,2875820,7609224,1242696,8237032,11482404,5240092,6744140,16242980,2545928,18580136,9015908,2913564,2567184,2956076,11739280,8402820,2507684,8283820,13163172,11131604,18620740,2937500,7928100,12677464,11019820,17685732,96068,2021668,19204692,18391412,405944,19011164,14174828,8951436,15504984,18939408,15361472,1102588,19873884,9840388,1675844,2679240,4829148,13009984,11168340,11784868,9169488,255440,3870508,5869884,12250648,12032204,15594068,15269216,14182624,19133168,8174444,4293920,6433960,9006700,6391132,5440076,8683444,9939044,10548132,18253044,15963960,12603968,1083700,13885212,12558144,7073580,1497368,7900916,9738884,2262396,116516,19710800,3526176,7285384,13572152,13986548,2123648,11181492,9915864,3868916,9890708,19403036,6123688,11818684,1813116,15873608,14964368,13344860,18016720,5331852,17143316,9689748,9833092,13532600,6024480,11505036,9655056,11148964,4887784,8875572,19838964,9033280,15607596,10262796,18382044,7348956,15013396,6160556,6808916,3224408,18769928,10737472,7713652,12546944,6148616,7514428,19912636,11702288,18223324,15641596,14267552,4351428,19775940,7456660,3406068,5943800,6590812,19993760,11454904,15881324,11119844,4729280,800992,3631564,16721688,14835252,16723524,6260100,1770488,16777916,5655816,14852608,2630724,16573080,2221052,9703552,12133048,8498092,16193180,16232240,9040448,10047040,12138344,1937368,3758708,11583996,6832620,972548,4902980,3261092,8467280,6530412,19583008,15680360,4001328,6748456,4437416,16877488,6831672,2328068,18201004,9645136,3736300,3454392,5988948,19450496,5389560,2546908,3574592,17928304,530208,8209600,11855592,4561492,5332076,14165228,17243332,4730600,17581548,9019436,7289964,9322808,16474380,7108472,12652452,17833448,9463624,3811936,2870552,4458244,16540360,18611716,5719704,4099912,5003040,1235380,10670584,11137140,4534932,10200924,2255912,13581688,7145008,18801840,4136732,2353372,1890208,12053880,8604396,779100,5455852,7910388,17378976,5249440,6109548,6556832,3402436,19023968,10741384,8077532,13782784,8628120,13201196,13547744,3931512,14055308,14785888,17224692,1929676,13221020,261100,4381552,14995036,10302164,9157324,7884504,16163228,10220888,16000676,3697484,7626636,6834408,853676,16960624,7169848,16047048,5385020,4899628,1473136,13716312,17021772,16779708,361716,14556868,2042828,4809088,18521804,709048,11036272,18695936,18599860,18852048,14465644,5500684,8285248,5081568,954396,18479288,6701496,15311784,6951820,7096524,4396400,2486332,19165712,6704008,18380680,14462460,1912720,166584,9047980,1711292,3755752,5397356,14217296,15735988,1846472,11917428,14886616,13256068,9926776,9206568,4505056,8653556,15510140,19820284,16527464,3444884,6110120,4854952,16599672,4999368,19708640,11986300,13761228,6309412,16381316,19864872,11928352,16199120,11497660,6431808,4841640,12468492,17590492,4444048,13614972,1780604,12449304,11708336,6767772,18224044,19444544,12004416,20036704,18332172,42852,19949004,15932028,11739652,2746988,17147924,17354936,19993740,13653004,1385556,2338376,11772652,6106308,16889368,16903824,5600048,4558616,2504664,16209424,1115864,7241056,6480744,15193216,4448328,1648036,13472396,15631340,14348644,15221864,1076084,10639348,11302208,4546476,10161540,2507280,14107512,8117888,1040228,10085372,16196412,14263172,8276872,8526352,5158832,6661300,10165196,10437948,13988388,7886952,16439692,225836,16225576,4700212,9852096,11735128,12660572,4605120,12470388,9841704,8683540,1887640,3248580,3654132,11083544,8454140,4006436,9969852,16637876,868408,1466412,15998468,13523644,9770004,11116728,8860528,17050956,15915152,9131144,11943984,15298056,8438184,344120,11074244,18814748,18107628,17943528,12886228,1357388,18391724,1925580,6565936,9495104,2631260,18394392,15358776,15769964,7698388,5694112,2507936,202540,11793304,8392372,17189824,17546040,11456608,16872648,8207052,19117212,11349396,18902788,15409676,13097928,3371108,17351460,268452,7279120,8840944,18218792,10575608,18622996,13053252,6837504,10500784,6687856,6840612,14472684,1900864,17482952,3280948,10363624,15272936,16897660,14102352,18330360,9825716,7435920,11112344,1455904,17783648,17371768,17445236,9827444,13978208,2216564,3877908,15502124,15227268,18000244,6374412,2783144,1146560,15041944,15440068,12963148,15589968,1429748,8575684,7911088,18681672,14094496,3590952,4125032,16228948,19429692,6689232,5416144,9271456,11711268,14044716,6212128,15636684,18942584,9889208,10631568,18728088,16814376,14471672,5769196,4746928,18227092,7572360,4428468,4890904,4716420,18289776,5941144,1105020,18579484,8621040,19452120,15432884,7687632,13859288,18164128,11283304,9864968,15637976,13422344,6154408,3164552,12963684,18026076,1961040,9639340,14910616,13533204,5924872,1250760,9357820,10355276,3001964,4509460,9519364,4832548,18684016,15986544,1217968,19593860,10530484,3286796,5341096,11533052,9429588,9331260,1308408,1265884,984180,4585176,11702120,5162492,19495336,1764588,13854160,6068668,15666512,18621128,8959376,8831560,14485160,6468856,10390724,9331552,11390708,3142648,4738292,12047892,10170972,9608420,2892408,5916652,10840036,7254780,6132756,13735476,1560296,15386104,17822944,18556372,7254628,9734928,16162384,6413808,12087364,16079280,4565960,13096540,17931424,4574552,15132076,5496676,20142456,9918740,10620724,896036,1419444,3870228,9532528,1693836,11128128,901096,5189864,12425876,6443836,3057292,10756228,14190020,14284516,9661272,7282368,2713552,4539540,3433708,12294520,13458012,13573332,11315488,9126784,4980016,12380900,2595152,15150336,14642256,14264708,18409872,5473932,19267172,14723764,20185284,18274588,5366380,10683112,17495184,5302912,11761940,18094032,6373672,16061116,7679972,7897180,7496376,10142588,15869428,6311392,12697852,16714344,5631256,16448108,5694580,2441564,17569236,6107416,17097960,8704068,9412860,12601424,2190768,2997148,10987036,6145500,18285296,18124448,8119680,12389736,398044,17035448,18430152,17446284,8333140,13106368,474980,17616240,814892,2579744,20181860,1573288,8306064,16555632,16047732,8287376,9265800,10206848,16778340,11668064,3329608,20005788,2717380,12093976,3569204,12573168,8914072,4756444,14449116,6306160,1915100,12518324,17438860,18497812,1401948,17471508,11308316,5210420,4943640,12293804,14798340,19273852,2504988,14396548,6710476,18430928,5024628,3260100,2961840,15972936,18255964,2015392,15766548,7414700,18860184,8623140,11865572,821188,18888656,878132,3398640,4154376,10065016,6717204,1533052,2986028,19406464,1458816,8889688,16172088,15051700,7462560,6849080,3381344,1477700,16653560,19859700,2254584,17606180,14301436,12901932,385900,9164564,3712776,8197352,14513724,16242892,8460272,5527776,3121120,2952676,16960904,19953940,5393016,4287624,8062912,6701748,1768636,19663096,12309472,7946108,14798192,13795112,3062224,15510724,18191456,2087144,14985628,5723844,15621976,584884,12617456,16058648,13076956,10968608,13634296,13002288,7521576,1891528,9577524,13988092,11549132,1833096,11432268,5542584,14751360,11947040,14769140,18620784,505324,10338820,17498992,15798524,11854472,18286712,7540148,18579132,13101364,862808,18673772,2919948,7565512,12058352,9746492,14413900,12524288,4121344,16860380,18349120,4520712,2341968,961960,10965344,6404516,14732952,10976376,14551676,18149040,17830616,4134260,4146384,3533784,15336088,18754836,4157024,18776116,14431580,16967100,10856108,10155160,13824304,8940608,17981428,2981140,3633388,2809416,11581112,10218892,5846508,14645132,9307832,10098572,9067192,16539940,12856808,3427784,19725340,4533972,15923512,10667380,10192596,11812000,4538544,9252172,1708128,12493344,3070816,9557888,3682248,13506128,5707816,18780128,3942188,19300008,15529948,18734164,15438020,1305612,19869444,9984604,2370324,4059320,7877740,286020,8690680,12926732,6215396,9602044,4637336,1495356,1984692,13244056,9268716,2296708,10871420,20070164,4313528,10159788,20039688,8286216,16681900,12812852,1777920,16709532,18624552,384728,13978412,4575604,9920664,7377936,3696972,7025164,8596092,4376020,2592260,2166596,13085232,11144876,6412836,18786028,19441592,11288640,19729120,17711100,17579264,13986444,2764764,267840,8298460,1916340,4368360,5123532,14079744,16686100,3199048,14347476,1436828,9271752,6818240,16510136,11143560,15713492,3816932,9710876,10428520,8280796,15773236,11983296,107968,11552300,6650976,13517888,9720160,12532164,11679888,2379880,9613980,2167520,9094800,17207452,18539836,14849056,3482692,3624840,16737684,20536,7290752,7636656,15314384,4790056,4643316,19705292,8570480,6217484,11425336,19781524,11577800,5586056,10314944,3365272,17902656,16014984,18550404,12275796,16161344,8793172,1717720,15548020,8262168,19959776,10385268,17084764,13458756,7267832,8284976,3067248,460052,17490056,694392,2308888,19387780,19954236,4106032,6567408,12623072,13248100,19420908,3457636,13201364,4614220,16143712,18269936,5348096,2563400,1246456,13189104,11294900,4872604,15913308,13996200,17527500,6251292,74768,14994428,2071224,4291984,18362716,447664,9479296,15263808,11212836,964048,12245604,6496664,14921424,13913840,400792,10434324,8276112,17353808,15156048,6444104,7175608,4243096,1164292,16679800,1425576,5179736,3298856,9448864,9047092,4481788,7651196,13186468,15126404,5134984,16432796,2488076,15246120,2727508,10431168,10934360,7113628,14879484,11207472,16432092,1992828,6190492,4824952,13635560,19441996,8113680,3078264,4620304,5257860,16672248,2164888,14845496,2405164,9140104,7550984,19912296,17684584,10050920,19506216,13751276,7184176,12960568,13003472,20165188,5621188,17039212,13778476,18589220,10626540,8389816,13537856,7908576,12386676,11428848,18464740,1072508,4792604,6094472,14333960,18043020,7854768,3957240,3580304,2660036,13234552,13419604,11949172,9947232,6313456,16315148,12104544,16625892,5251756,14502492,1626444,13756400,16097568,15237916,17568416,6701644,3458904,1634424,16672136,20051972,2952576,19039316,17552252,589440,19047404,12568988,6106748,9888088,4493936,991260,1548588,12085048,5942508,14982192,13714264,19103436,7540932,2090176,1967008,19015880,1791896,7517808,12647160,8668004,12161516,9197136,15520172,14943160,7860376,6340880,2147864,20016480,12294504};

    int n;
    cin >> n;

    if (n < l.size()) {
        cout << l[n] << endl;
    } else {
        int s = l.size();
        l.resize(n + 1);

        for (int i = s; i <= n; i++) {
            l[i] = (2 * l[i - 1] + 2 * l[i - 3]) % 20210108;
        }

        cout << l[n] << endl;
    }