x[]={7,44,36,3747,45228,630312,9953064,175687524,423979368,54676675,623084808,979843860,206550461,727203573,748572526,892708980,66690477,839692840,210114936,268182417,333496097,211122107,312612316,127503277,806259773,909104373,288131729,23186819,757701040,691908757,84043504,912445188,196796726,63183211,537658555,167930691,474863932,832142813,331203079,102380965,590957020,869242301,794063866,7092126,814625624,222749982,163779870,157679864,228382029,638365736,588097170,195650618,191860470,416685569,572382993,319416250,739989190,84039820,497608319,296171912,647666921,727128287,984502016,416717460,148215444,493244175,438960809,303204862,609161266,421785418,619664903,663813217,279834550,705847304,701631447,260361469,746042549,687518042,644227267,651851842,471361210,925793286,592802745,837113559,12032344,948708480,49745207,116252466,481673192,725682676,254798072,705547154,603129711,205539474,316484667,444170718,845193459,35646100,619906792,370815558,540625170,638563380,934526607,459942330,356480452,451289505,179222514,300361925,516884000,909401854,159808360,586938877,204386784,762528284,250251523,733148485,23905194,352066133,208189998,907389249,848679765,302691619,481587481,438906610,480339975,458999631,226927430,477026440,432607466,987302403,248576180,253731738,747263932,666728583,524772295,57033301,939196183,858540923,136069568,781048477,99429079,567678471,494343462,13513410,657362208,656906211,815067302,631661817,377773971,694182321,236176184,827490560,741401325,586878894,137617915,651488565,627922102,218882572,382088885,347211886,185179454,572739509,555313454,718863447,218998742,264200532,726890098,711695754,497134543,969547257,716132187,237201567,882123295,995491645,25942911,540669177,595715934,795850372,998158650,87584248,268650126,268679967,194562025,791767165,841098466,200827174,784143630,146540655,952537656,124518354,901155531,751355536,939439920,735213420,981897177,138931087,218596536,601655048,486985559,1157878,802699078,389096225,691037796,927105936,831932286,890577074,86130267,202186391,156150384,644628698,956950732,944547494,146222600,504539991,443912343,764023794,715073451,781622272,481738521,11318478,992889513,990616485,727108103,137047196,583265007,844326238,616343265,897022188,984341960,319503342,51335996,109805315,936431123,814555711,379664552,301729722,911720315,903220658,975096604,706720986,277698618,149568940,280821783,781318997,850994140,390509138,813232272,262551071,298947651,493816981,926272583,305618414,634931431,871104352,596397839,877159448,649979854,664773590,808303445,590572265,220492042,507607376,339644637,626736591,868732155,572731439,305666597,578502118,871855628,146715458,359110752,698250641,155517226,785692758,276858740,669874579,459034566,36287030,490136993,555857778,905926538,794737296,156325325,200494198,327909073,249124866,421852103,606545733,562634410,416575030,780066233,921439149,461472561,596810919,510805874,750195263,984110895,492662117,402593793,83228494,9313974,994095123,784933359,900912259,379950544,275448298,464786566,272818192,273523056,755646954,714359292,526867484,477590764,541432722,822497811,782242831,844887940,560475080,738753796,618385018,833698102,771262702,528347311,17176189,798774241,709857736,668827267,559772759,515246062,474864554,185591645,153881258,335002293,841971345,599357944,579733016,427781259,506991218,608771807,814359335,984120301,663092625,895372588,746096551,380866841,21587370,288460963,731166298,243636038,704668645,535493895,842924063,335166926,898983887,642178159,944498290,194742297,255448644,660393181,118818579,859768976,70100337,862617440,52166151,749692895,396576699,982640519,958551154,375495369,694124385,646494055,476516980,402881607,263471311,662172441,352013621,343599089,769593717,295823677,972781265,546752057,331347898,516171482,530734151,166517526,27197999,488370622,827100622,762970759,636267745,103934362,325439881,297845705,4590507,793832176,891899984,833248784,344266169,9391494,539734180,282767247,904900416,82479489,264410459,453546955,721832026,188722212,711701696,16568039,638783098,95820099,147322278,921500898,572370033,912700159,944972420,453690750,532259958,854414458,875702943,526331859,581532975,282035062,899342263,342368680,877178337,561382291,679162831,435173137,230412651,679860035,392577949,732145747,455424411,219506020,822134202,589703735,323591668,139757310,734906485,162127137,392424881,126932906,372149200,183360248,546094540,78028616,637377046,419201708,45710668,192422991,188803558,586206890,377543519,136692504,915806266,467799034,405811056,899978202,283193768,675448176,999485529,503148751,126797890,545508541,305999066,391420635,609290655,184459972,528505381,342800158,448912830,415758732,637371230,916538502,417771378,670618492,91232695,539369217,320240370,51253956,72925156,545270090,174885130,846180107,821992190,588839099,486585347,815303157,175719200,212017699,934606787,83198938,912876485,366855402,175394712,839534163,352312845,899158363,630312388,749157590,749131275,305879580,98331879,573725418,124678653,464606619,748710224,365933914,536480508,579511333,873981764,504048107,461079269,678713243,584072458,128199081,898441552,730659183,508175938,691452813,109933538,960235680,476714229,689678483,741647198,851806871,570697091,188203640,554502875,202287862,814375705,537861038,795738922,59366967,334955441,619399734,96329775,953696543,473758236,831789342,397187095,42003836,54123422,630559703,689346452,804357788,730629442,382152791,791666008,911387954,781062666,231777579,488775129,390368292,28370933,846332170,270534951,840573510,786136210,52060807,984464509,608613413,285733655,933009093,160932145,910497,754810697,558487300,374488891,421535385,711496898,575578509,669407352,36344250,486320170,758920171,717561307,664814764,978165367,562506305,787111041,728309781,670448966,552373274,591699889,375471227,231980533,778784670,284796073,130283023,217204002,162375008,500485167,734748096,90293731,557419500,26612636,601056559,817881142,910692861,806990825,455081201,368307932,182764974,761153219,237775277,773162027,453509363,342878698,478883685,95582850,816319627,754502892,787673824,750623251,372569587,325090285,368688022,697924424,270746482,456258314,312510641,852445569,689644924,370907561,450344089,437972179,609616526,557089943,157293232,958926402,530621720,416631140,393255507,427790906,840372629,548369169,458491536,639071344,808156082,433803605,533049775,53428729,735540503,32203795,827175554,444781114,65896942,821293390,611270757,836100229,502439670,708322381,985041372,133844248,150088104,947237550,781230956,911376710,582650776,710758870,329943968,377457781,733702347,813905840,901505190,501541767,53958417,853406226,518091426,303054318,818509229,138042781,481731356,353773254,338302923,81281620,15837503,118691251,950249428,482223044,91383445,384119702,75735604,137533753,453064006,252221710,618761994,688576153,485397663,151931493,214193290,820479406,752273966,494397773,473468743,182357624,679084333,449218629,108295097,949778796,14853590,382140874,465715853,232396436,291172779,479255215,461452508,382222655,949822008,493055008,856021944,759854120,38276780,73435263,236392489,887680923,601603978,973622517,633956246,596602895,97867516,800410835,195533896,316839114,323389109,6995353,636212488,889317443,660551353,794935737,6791909,511617575,177622048,207841751,313641544,578015806,562071495,932929922,159734928,852049568,711760195,602702635,548838077,312507353,909227548,197108370,617177396,258963071,335032997,317456483,405376552,142851387,888245902,140995024,367853341,665723665,142124497,345271414,77714808,510200598,458117330,972642716,320525773,814728350,323993876,451481503,67847705,70049428,881016071,701255524,805586934,911662530,647953026,342094670,344678715,773255040,781037813,46390433,336797954,205570952,215944559,1944020,38412223,907552514,437011602,586349816,783539052,571031107,775430530,336374877,447966746,257374178,584007873,700355747,5208188,112954865,628920399,501986867,695044667,955863004,85477079,380655114,584037517,151122009,363791020,104306144,750108053,120814629,618406128,50562990,608973329,303894947,754708390,197451627,128830148,817287654,277670258,412468964,543098425,144882498,811343306,409644810,337251819,154711189,179941323,349409998,51921336,598415392,367635674,344383040,261258994,35312992,661186551,691989994,926563628,743066854,162896737,299126252,552249286,729155404,449539419,796547487,96429215,615667266,429221244,566794886,796280468,594348050,17107778,888511005,591527863,521063530,585396392,977556829,524765641,232158337,900344513,327800538,259638442,556093397,176802103,481264447,333983376,185800436,475257599,779381991,150144728,350538851,192426467,604075827,146714343,657208916,159174225,149270467,541899756,676516667,673037539,499388116,182582344,769951466,521968322,764855162,496946974,653331362,736569417,585650966,334050256,851402090,842702544,628488540,999547597,244651227,268388388,234417781,14455030,532180797,214597478,922804750,802867453,444169199,266269240,75687075,239622867,943484783,414558450,924462226,760276586,411115771,869545317,626753900,946660769,190884318,855792491,800673699,952544227,651416226,154771963,307484981,627653838,756169635,101397144,96679118,232126228,696799527,176960098,230830514,781435121,13321186,373827529,452436880,927953111,728551710,326377176,709967576,295935349,657834682,825522617,96016520,708462798,361336369,715384615,30046958,842757205,42166011,224691960,979995639,414922864,569794283,3615532,740277083,189374625,213013469,652037977,998096536,530128689,472643466,40903033,421108960,92678080,26595446,235677642,515023722,747905451,65935447,951223451,696748173,652531187,137484380,78247583,593262425,856984388,760251735,251132839,478922101,482878005,253171117,232940257,347209047,907768519,864560068,628550109,704087205,546213561,240705971,93508194,386333398,735735949,963230759,35893063,686335956,646037457,512802044,909723436,897832769,82558677,126547426,959723820,873983392,983025803,295050299,500240564,189602503,542183030,49462754,836774246,819351795,357363191,973571116,777075630,919137077,810544625,94991782,537315038,823070763,599066057,78030693,694880041,145936657,17560233,618924690,508565041,898404313,221174762,228024864,451805907,717502923,983094199,512660603,438774469,285276296,252936405,586196772,457451140,528982378,162775265,66009684,542645583,976861506,204423653,65363081,615689546,869655751,510073422,795745251,338644294,260515858,68506082,398598139,611838633,84225544,375729541,219147502,772728864,726865345,790531112,625339116,508124483,654914450,696788097,265486525,842710781,563567880,852417302,805893718,386883927,538338483,792042406,313735170,612860870,819017550,243980347,587731726,160198530,663772213,212273945,194108225,705154065,523199165,642219182,717089585,772906745,455078254,961109702,445500698,731635212,251934467,622458876,53397020,974695277,840098015,566775011,369925147,84087422,437297823,492432405,230516826,270150872,447175559,784083046,764181441,636466951,361031452,215376093,764446577,71882492,944891205,648506894,201712577,470608583,499700412,405348683,640674545,784217555,35310093,833619949,356935623,865841117,811518790,64714276,331850239,741743410,90344706,132609539,551852351,740128356,205561736,578232384,857408482,995714822,644665936,373156467,15994732,375919890,857206823,845463268,868613724,661402665,501746314,190972023,291680225,974776667,255848923,108486139,458758795,185580224,612746469,885197495,774132652,885792576,205946853,643909926,956630812,631467123,798880507,499378834,738015768,271377996,265858612,482358690,96213883,686591070,153147154,606626193,365346823,612327170,346677743,175785604,311272943,148543363,224793695,272174824,409602321,586416194,826300143,77545865,46886903,838912800,584283628,618247973,392150468,745967564,242418867,693315973,38671701,419590601,269479869,334653364,602431280,952430940,355950889,696204876,813218432,935336938,917339285,629658380,578961512,991274864,429987851,39776307,395138365,330622975,658754866,858440623,188712475,674551352,516379609,28815511,110117013,591875477,954761456,732121935,359962622,664816921,481692566,713978138,595073301,931606467,155388386,549706895,775934884,473903037,544363694,860640865,532445432,62282206,365829288,60867546,861653155,110632846,531006732,652201003,985371040,236300707,476137824,277473939,835946534,780981955,647114265,882360023,905064346,73470660,599025053,851085383,449817704,770816949,278559947,298314256,930010626,548233076,269556134,555442732,255514326,124904406,911866646,786782816,173038970,935658839,15703139,856704836,842632566,588119433,481988317,693758721,735201143,664360168,39349078,847297115,849418344,55768033,555784067,201312822,314672887,266229722,684160533,194310752,374042357,282654207,614233991,968977585,250101595,799470155,241326507,798323691,174642076,644170735,526418120,711289954,782473039,30216174,183868555,231455683,692174790,994385082,23791325,964976207,689608637,456456252,407837036,70794471,9053210,204913948,238649993,979143210,182386611,313723126,394218653,240549561,251248202,487022127,244964267,395674225,50367100,684928144,497363024,596512828,743701657,393832204,957916874,533117037,769611659,834242352,506829886,951373385,554501745,893096121,877464183,668562105,140060318,219949337,122196355,403407245,733604766,443315432,288366871,310116398,730617428,796117968,845553633,922082034,254879658,294349164,247602409,820400093,462226760,196338153,241189034,310517725,818021598,868850635,878913333,150459197,967500216,853306741,573667251,402602297,257447612,921611063,429429527,136222753,973124919,764728959,436384786,889718177,649309813,652187173,19373800,636382405,35253098,40755486,88231038,406827427,253672810,655740259,977601738,434969338,170539175,31325791,772041412,966487257,859866024,319522976,549978905,193076792,174259904,769727168,3282902,452765470,15938508,653825646,394312816,535201087,899750067,908536146,916037331,36130530,913802117,161463235,755762306,810496795,429399182,853660622,65143294,286545888,750730232,217261350,786213958,741208396,891619891,69332434,567642831,596942972,870185877,687239542,84107057,87017623,596962070,663687744,524272412,962672728,925945338,731063348,118946568,144249504,57207074,98943257,132483646,743531374,778203803,887943713,114617391,357754364,68901379,617930725,304521681,843887763,744466101,917429474,59811025,317294321,102940990,215166038,85711164,409186854,300783050,728545806,609036128,931217778,972701276,810423120,281837485,857228235,549546086,837520437,324364445,763250459,436964011,204050291,588690245,135589487,495739021,910361947,560106803,763584157,293993446,192751432,839785820,70800861,532371038,886479061,488961967,116610511,761368704,473653020,449879694,498270502,682275797,663533358,288817282,744508796,205750331,745783670,451463239,432396159,709848436,844970413,416995995,706560224,919546093,498863327,678271833,32808569,64368316,317979751,828050575,655922454,422470464,86247018,265412803,962200886,462348858,350751094,675810502,837972675,169839103,477083845,165815942,834061809,488317237,136962674,613234602,414946072,767748458,571768454,830192632,238350343,659811584,341438554,843158649,990674326,402976651,660346944,315293012,246685964,432280342,884300750,119460025,82819466,945078566,969897675,324232301,690947736,177311464,137129733,125299222,483579847,176829938,521059024,492573969,397103920,477267597,698048290,179138622,876270268,934296959,788562640,554310742,385368874,81941816,389380656,555470377,191077606,749430319,667673582,151411149,603759800,502054361,124193854,322630847,845958485,413722949,283416591,116334169,175682739,143538515,868484425,524535063,845615857,934242929,121774151,540936551,835924522,445556874,552325443,394670674,202108381,83854840,376576614,609419076,806580457,386813550,286309093,212451714,557883932,119635989,51977603,425263893,534959979,75043417,94314375,798021428,112749354,156329738,539404616,543182501,358429024,69282759,898837840,287392993,240437172,298161411,893421748,521777193,229284854,451422725,356933320,488434434,498643876,1612794,788137134,836663215,424133041,938303393,495742019,686666177,576627418,874148264,717519780,442095996,180608904,670533674,551454272,663878403,838673330,192654391,23457592,227703807,667951873,120585559,917524777,946109489,213098704,141458577,600524562,842725441,576046330,11324399,889396842,301735925,823365109,489973862,128488355,47772299,789774513,896794666,528738171,509264671,572122675,846697113,581360118,473192231,467749217,359205674,88864817,364906712,346624845,773420569,829750201,613708794,617931331,593043790,944583417,833174565,954488655,36515326,921215688,899544049,143309339,603887913,435878379,133136726,259887809,144534239,21503602,144930661,413347,938403069,917863539,387205643,590037735,144031241,531360641,151851313,785182122,807734849,315808088,356365888,485745243,572643078,869533871,724814647,413958817,489819870,201522052,474851786,995518009,748397308,41390228,721521308,353142510,270855350,267821582,284270010,124677374,706388119,13369902,260215859,485236720,838750504,321484023,612362143,86330894,468569279,566373039,398953887,129622059,848110883,901333677,61952666,476024033,77290266,950118844,335513732,305150358,865688482,584619364,395604995,77985618,19045728,781064180,615047106,324894041,871804971,852541116,679595103,330050331,513396016,852218097,795154367,643163939,275205154,912106314,176534747,578791248,851998764,483193765,115335806,741594469,141577094,565701519,594017822,460424996,117253424,694512570,952803480,783548020,972301667,143365071,165597068,65753951,131145938,432401667,757175898,311708692,154825702,585890337,733156190,143939139,755944626,792176154,731131406,579775447,426344726,732935883,511973769,613410164,894806106,465385018,522056171,142636773,926919053,896874172,614184057,940130178,362588850,225729282,398219691,231598616,615540426,851981898,797371478,820694403,784701317,508067209,35624988,935638977,557163711,215198742,352754719,322529487,38822837,241468827,913759743,442306027,590995455,156832097,445596737,755428696,712498798,206276995,90584329,647039791,206900940,135430005,425758533,719361347,57084565,382142216,776807323,53176603,454567573,595642829,709653379,849773856,462184762,622820990,514582715,974159761,299837004,514657254,67867591,380505209,997569207,172292780,215692757,581313797,74043747,521711664,518186318,126417995,657012262,446121547,479690371,230291829,681877127,82919934,823806459,629614985,196755635,496993909,711830393,656510416,230489294,528574810,734338321,583945134,875085907,484994526,609190435,864966419,111192493,440660349,548902939,870275608,587644577,728272485,255904415,844792201,801672555,578348473,749858842,138627759,933590928,96444884,963120928,565134738,873093907,952600629,71841039,973698982,913144036,942298735,405292172,813616169,248929996,948922912,861020710,378975382,22173622,915716190,695792963,240668937,549884501,873732454,70307526,976411379,758170777,988665232,327591414,299946028,698495876,850891518,369104708,764249454,825079772,629675734,566006762,224754541,858085403,185308642,255126524,95624457,572590467,928907839,171044907,170093082,296586869,963782341,562746992,625169323,169323364,983976226,141557968,339591461,427368141,972198850,93044808,860410799,460910125,208924776,474481629,35580505,970599233,652930535,877821546,411585156,22453677,994439786,225914892,540775000,458478806,594546977,723317161,815625687,858362627,632659130,228513068,696596901,898663025,726286497,825151501,387495029,790191053,138522819,709564518,765508323,570990630,886843144,920976450,55834879,250349366,963792729,537522354,187463767,94266064,249574732,930000127,84565780,529244824,266588253,642513513,680122160,861274764,692395049,662138838,244236260,529613877,705886255,440155617,324990008,985515198,855931590,170745104,964161937,816838334,615823143,175978523,498280522,148907215,687661432,704111464,715985839,256310178,432950011,82376583,722462590,639068744};
main(n){scanf("%d",&n);printf("%d",x[n-3]);exit(0);}