#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define wt(v) ({ulong _z=v;do*--wp=_z%10+48;while(_z/=10);})
#define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);})
#define reps(v,s,e) for(typeof(e)v=s;v<e;++v)
#define MD 998244353

typedef unsigned long ulong;

static unsigned const nazo[]={
794320701,622575258,951634768,843514961,342153607,856268995,748266321,868403257,778711109,818259698,335208636,547731907,484716420,226192128,363206579,388300350,20245055,24381510,818643433,520327117,146033674,799060416,83928612,339746732,153940170,573229620,802444086,838105459,810477541,890645767,669455065,4328724,243500204,805377719,957284994,233844333,246451027,713600061,524654928,55301871,995966343,987644494,569528325,444535114,121801869,475527595,83321413,518640959,753871986,616581839,87657090,335095198,329476019,422467979,85061919,121877488,118958298,504943262,824826487,331646456,629472623,305601990,8132169,634642305,701851262,710155356,493176569,442227217,126753816,619438699,792011829,607118083,215383351,254032477,76070219,12170653,208560294,688980715,972543899,360212833,710625022,930619254,223475704,12287734,136104833,213677809,742176898,437481119,844014991,496755126,82476628,407654956,276163476,484666570,358303350,733984504,847665451,379798502,130487418,807905799,179158012,113103368,213708793,840273765,976676070,520300248,84461090,401517118,815335616,163010114,507149582,382643142,588472432,869368312,565331944,486181760,592433610,255195939,916209157,987331938,949077856,752012865,461682956,971666045,461433599,266224641,653650659,59722294,507489548,492796729,718344791,773065458,135793162,332466175,697362089,165468985,154284985,405191103,474982354,486017058,256557490,527346740,140421112,17830800,602999404,63148540,589659908,852710733,167554312,576607908,952546534,44334978,67426455,576395965,947086789,299151740,598632624,308154538,175337681,820268875,387073923,341055267,775941975,249287218,348638616,827969585,830878965,155267990,530838610,196875103,733772024,505670527,320565312,346372399,154764022,364022742,171650904,162692744,325946380,430274379,629927932,321034408,726565408,401242844,687678328,875471334,522327866,276469005,288557956,26095063,644814801,902017136,850125134,76272367,265501765,808188302,611323334,481518618,110403421,637290875,968486412,687642897,368673754,541350079,238968091,244595738,508085531,605693897,774729439,578992275,885124142,87501853,167464579,673640969,95475870,559753696,365734297,988684510,556743573,516947926,122051953,687770052,441780683,653058972,600441204,496646555,498409693,634382780,19436904,716370309,46449582,704171047,475436738,219686316,741309828,214687007,694054607,996036728,388135581,184153431,535152252,740985066,340221162,64487202,758397984,936305091,546618776,936449302,470291757,573188701,127331541,477635889,594045086,138373508,920780804,820889369,114717548,244472609,434461784,767085877,898678134,272770197,6110951,926921945,371439047,769276277,650360071,228582968,250761874,375501999,190354032,184688644,382851145,205142246,830198982,169652337,70689911,290214667,278485930,433967744,511608065,304828364,548476303,228954268,145928183,208139529,322227897,732496130,559467866,44321026,439130214,751924582,400242185,825173968,619860971,302912818,661924303,232490871,832961089,541761147,609814401,490127653,667534394,443546096,976740233,244494151,716984315,174445260,856718208,7881526,621604096,582980894,459169773,519384688,513299260,414508372,676593807,139406620,554854103,730855976,345045747,801218887,942894918,123914548,277607958,12425497,438592205,788985931,686675781,448950441,254746329,19917187,996393717,885846336,924655145,167940004,57091807,93467279,415589129,211568483,433562258,836622143,985877736,714900441,304000555,196823434,386175090,454082945,283276272,59798124,961516786,805150194,800633922,963811126,432000949,648829080,336338144,205858065,468538589,99693027,605591466,114817285,329354408,743642938,127900446,299486717,798888208,933758174,410781855,869992511,160432402,887012936,336412095,581658043,900705184,478435584,540343363,311480517,928327380,329798610,562504097,543746650,722406889,859575075,346854922,502108461,901797257,216172793,120469680,45217381,493975314,259582482,673390095,639013626,680891976,309609915,101905464,22386077,850072337,517888516,596423353,125905978,430461062,654771264,136004560,391312514,364326409,215711291,648199238,519914702,926259861,683029439,747961468,449438910,135201395,582572059,248115506,39518211,782248841,632588700,325641056,253574313,848145179,925900767,906497220,434654276,395682459,956091673,682072039,706942055,595658370,895016274,478827891,736119664,274247897,434348420,128685330,679486231,773824272,46991271,770953811,519980706,959795768,892454425,537551402,556459292,386397672,933166238,760985706,434809274,868976367,685344315,816463526,970320037,78432018,41837362,103299972,455924042,42832137,88968548,262583398,482733986,124232628,994073613,817050633,958342963,640203039,613025580,28240545,154080589,219822875,951576874,391175860,184022526,187587710,21040684,731749202,872699951,384349452,150579253,631942882,363605462,686240628,706687787,204510812,536841513,806045836,107043716,572826241,72928088,392435201,25228000,312979316,403505828,62408851,330366200,797219586,755146728,630543163,327370780,535338453,867196267,45060603,72509770,998054543,143569941,4401872,206600569,896619295,321420125,801501360,3985633,583611404,123034575,22721999,242317564,66251191,881980613,257538505,39902177,727672679,231726457,50544263,641607054,713773259,110711463,496120165,364850579,728308844,947245330,634202826,42826141,483331321,427271961,277172872,966001021,109640507,903225945,491099065,301162906,399163610,170907199,824970047,532708555,749189706,726851079,556100471,901329808,995742015,290758984,819365833,857262276,790079698,312302876,649940889,869387315,561461742,860770853,30538685,602084700,545936768,628698621,904485069,58425874,515422754,390964040,33130297,21177152,517043958,983646451,751570518,62703797,767558983,381621440,830544169,214431262,158582254,538670190,268075280,639984006,16924946,601311983,11932858,676779422,208668669,907848813,718559411,592104546,896907881,91402852,652440696,408760370,381820550,184668555,403111340,528658229,319771938,846535038,469212383,450954770,567944994,45098521,39431727,113353651,246260417,769000532,737888736,761181575,380458466,92778720,80185092,31447121,326483885,201356677,303707323,963411729,600224654,610788242,193395200,676717141,286729639,570422406,845720212,80215647,167798184,170602427,980063727,33247703,527176770,662831075,59342992,35943296,209399588,27377140,819896925,757589285,345818427,46363831,571845573,646110296,716960122,260490556,422691293,218972570,412557048,524053689,19702487,563227185,189134712,486814173,89788117,50669984,10329999,743831651,5064775,704349713,887754169,208654897,384556523,968443743,74642936,825205866,494912011,921494022,386913575,482155763,966181397,899294628,270109820,738527564,721601529,426426867,444647376,420363732,66658630,5306207,749693010,930491589,739646301,546293400,85656446,440296067,433136397,123359323,142880239,970507253,77587117,672712161,919268055,548899918,795117413,649284776,619381636,596112265,475843543,29177886,540116380,363307997,930303923,727311928,609649620,445241944,730810931,158149591,869656495,342090464,82631039,771452494,242283133,710180341,10664209,347936819,158917940,404014633,629201235,697228004,603676651,657274520,159413990,716187516,333653752,801164469,913410624,445372941,763581884,189981543,97038001,199130490,457957124,69860812,253175310,623420138,55835676,186891491,630700446,333559109,408184764,398509966,754859105,945620613,538450044,714343719,474489139,409330795,631525673,187572091,441142131,486192966,109193920,715863362,319934485,649309468,882121225,685439664,480105511,45670503,86345590,290623190,327447163,176051419,633480514,249587584,480494095,797384966,576958350,215196984,932260882,582873473,846299468,379103360,123922842,24573024,473788547,368843507,909667780,64066643,841287949,365734405,619831275,881924121,80745648,79416424,529058251,141821953,84848961,16758085,799005146,804862330,930183684,343618790,46453782,950732624,60557616,72391155,720110819,179798344,133593586,786244324,115532636,162360166,204226135,381817992,751173870,440524657,644646247,718005513,987398041,288380410,559476257,153043407,492328637,143012340,546538499,585186844,885372616,836309296,484646063,992946644,938266899,439052427,279591854,119384945,826326566,293086473,463413925,98209631,883648784,451231137,433274228,487500669,861181488,5990398,19533333,360394220,486445643,127888317,345951083,519183603,172228006,88760268,293618704,168251188,122553056,421873244,333211545,816810500,460860026,750214837,785747109,82927315,320948771,45629542,703004804,959509121,993102146,741149145,659453934,570235969,199448812,685698960,200922936,355263575,606007397,275877938,931665156,726060963,915285229,755247071,465995780,391275282,888968816,949943829,661211894,279677282,874210253,545343574,524758659,852740983,781298849,156060050,218847324,645691725,175447156,274616135,164725213,876259965,134426085,740486281,70834700,201582064,163283995,100142684,493676142,30403475,330383597,567075034,45293087,633952583,97023567,328864246,901992112,502130159,344532358,669261087,874160284,359494141,518541347,792613408,542284482,261079830,475692408,983888689,499701,972902860,180268136,630629216,476473360,246950151,425485256,945252568,260871657,847343423,859656957,748341385,445864039,467240788,663999657,982269943,534628228,489487221,966161838,908594185,37694879,415169242,460997984,991600789,550515377,988879122,267471630,914890559,74946310,593257754,908715219,9375974,471662844,802010657,341090800,567079042,125452098,570745938,772451141,668125031,260222725,965538271,705029620,372444094,953137160,360466689,877023861,68262860,299136328,170600412,694926702,972960289,640824257,870892000,49349605,958219064,886373431,145360045,491158116,813735222,216899325,721591430,488974833,189211556,543626106,94895376,375133117,416134496,846953973,895618557,914358877,550939621,890142670,912644046,279062486,267087499,515998138,443302375,59222623,209104915,131454175,883678682,974379140,29867988,361345899,52681490,987616543,973028846,461240564,616382754,214665618,778575027,789456453,469364208,675498774,892519594,641157366,209354972,455611175,721244718,554340829,519429436,183120070,392103392,140855970,633410162,202488477,180452365,472163993,386661727,407401415,307555075,246102127,839297057,343186496,455190632,45101256,542572824,459605985,759752084,865950640,910347909,495799479,631167915,39513561,147020270,61538119,188976436,777379416,319731481,423075278,192215679,692630086,891389917,653081583,357704881,725559009,657197023,555640520,866828783,489655367,618746333,741978130,470873712,857162530,651711978,519702193,979540062,499167203,147377438,231584414,600032735,58362753,432297457,66739338,789839417,229989603,963280922,126483758,823940735,854728194,55521580,417102339,35509631,380121585,119784842,891793509,476560206,289735246,538836606,680039676,258068354,565089095,567225178,894035515,184149740,866483750,518732813,530226794,798841689,612058093,655296284,652898517,100200864,869469336,916612912,831062377,273385666,400003180,602034405,665523189,363820833,72516975,204844389,220355566,169791838,824230762,958844889,751048367,711253603,27816450,240422234,606414889,639276200,479999175,595894722,869373609,957659577,856291182,151609208,931184650,973775059,772483279,585903222,50796259,105044133,331297418,465830065,321100701,885604164,267549763,146927737,119147567,479308622,330808598,352236317,803165566,250030936,492850705,425117095,28411190,655084504,355339291,108067582,231049770,593330794,70556527,976619482,4110926,420866308,471267775,730631766,360302939,466842602,655060107,532727036,330788963,976011990,299854060,367174976,99112825,26603047,132957646,349681789,613340449,471224040,888273464,679766163,904729112,808439099,112866100,27009637,461982889,606861249,185642553,165258677,543413717,940726647,865620317,162838496,483773490,772402336,558360293,524452671,942181310,894656849,159682048,696443820,461662659,288841262,215621835,815525760,830311866,375346637,525262321,762485828,160211743,838034688,499592667,670276733,55455935,283762754,382193112,848465414,772939450,237733194,658806580,895661387,802975138,635247147,308608342,305518593,68423119,829443537,629151003,41679010,770777861,193785380,953370929,939787341,633019115,761608180,10030124,941990496,817314714,159521308,32992078,281155967,811992422,455490880,407977655,797733565,746126874,599168404,657974861,109345311,523251759,36723651,566942325,590362346,677407986,39029290,566408286,778057888,531148132,202710497,644911642,970108333,377008769,644086436,36266249,140398044,984674234,890685864,372735784,953998282,244666780,150978783,679395002,191533108,4513604,817121451,830779970,115878924,60237116,189106765,532559929,155467547,645094397,750839565,839372883,269398781,801003660,937235617,34832128,45380286,419865793,500748445,808840298,505679020,67748027,722823602,475192647,898625356,30707468,510510079,874811171,887695577,241950396,785415093,459457310,123443277,289002995,942101309,44058516,945423589,460564447,691202878,993747402,505127379,877026915,811613669,170719643,43346902,825249534,701065652,894686491,172415079,616420842,479884466,818472485,33100406,785656561,759233152,910808453,776136287,60276255,112056822,30873582,264932843,725013930,280432904,858514130,966416265,536026399,744907854,255879376,760011683,204543645,746726468,407025071,773493450,484115640,779955843,137054066,214259114,70335649,986221794,375656780,937829887,39780807,74663418,856613288,663749952,586500750,594857861,41287887,707248860,363794505,214079443,931176409,441119352,322926177,703841963,650599032,320455784,951867313,321655191,189154221,782910283,22730922,193976413,284479462,633989497,472833085,543173021,376170917,843974315,277103960,276337032,618085330,709177581,934235235,851878480,668188697,727570930,340451804,210980913,618088037,167901120,377244569,631189048,172391301,816924115,768361101,4140590,825706314,710616731,48792980,822293368,728848952,609398037,198183883,424694988,673832039,164882207,467166122,390779739,697531369,854463574,971857762,292107374,928647832,172816665,473638117,172634704,119912226,186745347,870363659,705101227,846430373,111739787,883036258,295817828,994747341,670091685,961832171,569838153,827913110,648321203,603736651,636266130,155561896,761149555,971434307,215943884,957581097,238868485,123938497,222270578,291526483,296432067,604092584,714632150,154208384,916094663,379031284,784443601,276779906,474644672,680236576,29898096,403846507,557820245,711412042,490754666,476300137,343446026,577560663,794428640,449999731,384052241,979099216,584829004,884291360,570756513,837505660,239189677,308461578,536735424,565398835,452453542,554075104,508798743,221494423,135613243,185746740,743644974,637455559,387848505,75419858,229041341,807199011,974536974,761396289,817297923,683200579,949732831,656811754,163238015,868060177,655924264,142494854,126483744,908213056,417571152,172251749,905866808,759615359,119439390,58880470,732510674,425887661,146493231,10777338,98375358,287201690,375755689,133324240,930433791,238751726,494864414,871812268,187645405,253905932,149213101,629658257,73995346,561964510,375030646,569877248,538365625,894861037,432778573,601051164,338039963,323165748,890831446,744824678,961127433,163699745,196977789,326935685,753775398,776773193,339098436,711156774,187702422,551117190,709306397,70480616,714854509,917730873,817025522,268096534,718687165,583938637,688165808,716476503,115280121,34098205,723774303,253300175,473722781,592181895,239705245,204813933,343330052,677713529,309927554,42620118,625970610,189934488,768077908,153858103,109786645,10142042,853423086,74442537,681530851,739654600,844536494,242602271,80509224,464294976,153194678,846803794,277655834,8764365,857263130,11648914,484130271,588157748,801660479,323319222,33983922,53436365,286127187,323445399,160578261,814863598,728536760,812214732,603351952,571682734,221534021,578860343,686620933,470144103,529389804,887077412,287813427,583446571,918553956,537063417,552122490,456657788,415728610,841398301,657017777,296767009,147815507,492442730,486402359,517057952,358117889,892729116,529234183,927905169,880488739,56052646,672501256,545004454,661263402,725066274,862704473,878405054,286030704,929489958,880960316,627648256,961955322,316128264,523401768,866348558,530793511,545840117,150048894,1428973,129997860,178914521,968531499,129964745,493192054,372157672,527099153,757089702,46109980,888727023,178194335,606452733,935087197,417013278,475013640,645068150,105015143,92824836,739320012,578148540,704670490,679634982,303923960,52444727,545267927,340139632,219781688,473422618,944260709,841458088,339503055,227204845,856289555,171535924,176274622,60154924,303597020,457563413,567321014,902105148,965863156,993934726,848766154,620062589,58009929,688639331,567324943,251631751,891124092,965004605,868038345,728073765,980591474,245423672,953851770,364348669,557940630,65939795,997183953,707582047,567754346,134355125,640462918,917476154,696827709,617681407,757683375,720412729,102829760,522765289,941672873,379901216,743973921,897853233,461114138,363644984,477775267,130795184,159155162,193493419,351010442,961888678,970117491,448622437,362061402,725917757,750397042,60281882,451565833,516525563,288271205,834091641,180325538,721350583,243121654,509738561,880082015,701005212,478765857,412402347,964706248,368727223,350245997,770841539,285963267,168919049,96680598,4253806,797111338,911986072,90611923,734916401,49385096,463134614,392283150,727147832,872119550,782722152,251653209,22339642,924893523,619962700,904864025,944607597,293712413,55893129,710819346,431448249,640606702,134743789,737484075,827810447,875111441,897688531,667012721,137444289,188236287,649906453,162955410,924944867,128196719,458163207,520639419,856610725,284087638,879016923,116678416,896873665,399747639,496498148,233718915,673656292,994137103,775731204,326997798,231660484,261112547,308865535,242278291,293191596,872469002,844205986,338554735,761380212,946351268,322362065,303858742,648593140,145245237,996994989,950044202,715378814,33156804,774138840,120060040,234310316,965877871,814870667,995731140,752776907,109875812,944324792,604511574,399174366,954464682,305906744,32944425,688462343,699515335,454739641,181061361,595972451,320710512,943048540,884590835,373423411,888978388,758021325,189347203,94548916,515310801,16778626,501974989,520063097,149901323,771872388,393097118,264245598,448794593,672140820,665119292,958886874,810961627,562626660,289396902,889735422,370710235,133597369,184864860,126237931,638157691,812621549,628431596,187815454,137140740,716613808,887299147,40821321,211532738,653170892,193001113,28232213,901923430,738875873,620926324,881193495,326086413,188721501,213607624,520699975,674357895,361278477,789678076,989322480,40586330,573336072,48084529,529279646,853591911,940422708,851239196,159243171,461276719,53981938,922152941,472619387,454582586,656617149,507405842,640160411,162133406,822357546,784728045,975557735,240142125,260561846,593680029,346931132,399244223,304154516,570526661,25361511,855991467,792685763,461709030,3123092,759597309,571973670,54771011,330968286,452148143,693211237,696745169,955352942,276668445,851010813,527136171,361878580,719923678,213955782,653685331,492233758,904928284,521439544,314116314,714694288,497773950,880863482,962314971,27058897,242601819,31193238,417076315,903488551,413232276,529049957,394191412,109810219,187380356,756805206,622782150,296063971,679346220,912054995,660786512,489527525,22681822,612781202,185431289,11346411,443000214,908017687,97429799,898869362,65424475,398584306,1139040,622248606,950949427,134713247,606595763,798057032,533492084,549226852,261018895,203977142,597726518,612395533,169232239,19077885,471716440,810239235,287346243,985783183,504370547,416110605,280168781,279735914,772272174,646448218,373489256,687719600,951685860,495394464,550834177,677451853,134270,69053409,561372986,47036794,836031186,729380782,951540287,160156486,646587579,940011935,227086783,908898452,586873325,251315369,123430610,691550724,87358700,977294547,452802854,17303599,211884088,398590507,376171878,977802236,671386146,911865039,890812669,262730948,85218472,571819898,882011908,137993227,538771282,231359609,892554611,13228662,753733955,293449823,565106297,880038260,422155913,292789649,488848873,462559964,319136649,389250073,902434599,218388363,232145044,410405089,65977421,196046219,873136701,924288084,950117011,354419847,738952901,901589870,229025712,279682597,240499774,836921229,255207499,140713759,876410050,89451086,815050431,286763339,205783082,203880896,764501618,821613696,693432689,712984471,878689166,401568084,105747184,969939820,707168676,118558606,192370679,257567013,518039311,306141099,900461977,633602201,820515766,701197948,800940812,194263312,663225377,852819309,208340822,250593073,343922363,64355747,865507255,882967162,917854775,160268263,367043900,426307652,560308073,482689591,123070117,630348767,869323959,594481666,380305810,120851154,452175503,692124879,154225962,940618355,987633178,525394942,958446885,459186224,645080899,392340631,986641845,572435471,562508047,148547670,472423564,501551804,412133603,808148421,121858169,406541781,5779629,465230149,268220450,322858514,617639292,292766988,948948779,964862895,891591656,37533233,609614484,435296627,697871870,831525769,376634609,429945782,222733073,491700706,433690926,102346485,271806245,230627123,806796392,158332229,431066189,364068110,281037625,948072999,885082957,273889300,921101562,520953985,451482443,414711705,983613670,338839282,278862157,987567725,341695597,316941752,324438509,645101925,208052766,93097020,745910480,366516472,93414454,643610018,878379656,543813673,79409043,795066904,882539768,959226016,808327634,222051372,492430178,581113300,919790444,450760918,135256091,317065490,978953814,606799043,92737020,760113749,40112104,594993263,377583170,726777169,609718603,600434748,929031749,498489345,260891855,231681834,142084126,596925236,286499436,479151984,766396521,101709648,801825348,516077141,385508955,580187584,21466638,582668184,71918992,454055740,450811839,326908356,48616790,44158333,757090426,23038928,159337830,498662578,722827661,390109097,824078995,550187417,676465999,351166746,858541376,484197484,142806355,335298556,260336467,388321071,277376296,902287057,160606858,989889312,533873747,384331329,135497322,515740430,399741249,29253732,830466395,748018981,894172275,223057784,861360266,794904219,503945611,914515539,381712722,37715998,294102806,446920445,713754333,383159695,222504184,159964065,315467220,411716660,856759735,941193736,991364191,651090548,291164517,89295148,984413571,354454419,955830260,525636882,793690727,745742720,643003061,208082782,334429176,685742164,121920026,802592886,933726134,980296895,952687953,203454134,531499294,84697525,958861526,585912124,406180387,548366957,960032264,234691764,835485470,431241754,730371257,776236585,917314920,352987387,782435790,530759250,133680102,683700859,756243002,389672911,92886913,155880316,968885477,781382332,481314940,335586656,384523991,666401700,466083570,852912309,566774031,339049538,819123211,464719333,373993838,231837557,291935743,531242935,336489212,378114649,284580235,887435810,581469426,962349557,435781313,867198583,154662032,642513252,53577691,151787197,391213593,882592520,718090279,646437830,617525112,566447574,205379879,343886989,381453318,83249451,319916922,60509069,189439158,834690139,321438109,243156512,923248985,813310983,977073105,73168181,661043493,491017319,367595065,121534551,601597890,43599595,520373149,242491083,117041257,657007679,156670881,850228858,263379659,958294181,913585674,228779219,281391133,667093830,917381496,678453096,841679172,866509233,904648817,39726884,608383331,963381683,978491062,837522846,642316745,988913625,15815703,43732017,474605770,766288502,734981354,933415405,739218032,41764837,597613057,969927356,929161411,479397244,943892172,654297850,910984217,509759443,265612124,733368670,726128118,272972729,575582196,684082285,511368847,739374287,44620927,151940310,239369506,191244680,163353701,555093158,917753076,707214464,4982431,321622697,64414846,888007994,64236197,709414934,311601373,714188994,974193679,663845061,832450443,722905342,836651365,595455714,121417302,386110576,619767971,400804438,485843399,998189467,178854485,68760852,315383836,552285014,33439728,948142630,566352536,481590316,75567168,930815748,747419972,343661653,922735570,918059892,913608616,654466500,182349006,854591474,957772762,253737943,922830266,431157050,461381763,839572812,255472135,945232301,841189771,749972935,291035628,423220325,261750506,589922541,242814661,404980543,417151291,480407094,526746564,277756061,43813907,960738684,902733683,265314033,702537215,478698630,632054384,539256611,88946037,101375774,325789851,193461039,175125009,787318520,870795136,952929110,886326063,922707110,115694257,180962549,144478422,144494576,480735988,970447347,802661100,392342986,372798784,382034539,858477553,909933814,362701668,917567069,430251602,504116465,135876865,191304583,109535767,515161142,93831930,119533367,336504537,764535359,78244391,906435960,312290372,334964686,488452388,141007822,649984054,74140901,312507181,255884586,881169308,533122565,351197278,988562774,15417653,426136314,164498344,551157661,421743389,118083904,799749262,536473301,59993072,761666974,919466156,724222321,696526779,649734215,475133972,893569039,794867956,190855718,288714507,699404429,130738471,887906916,784847078,960099002,255957349,165410700,982828,168726708,930863266,596124706,422755078,960585516,495702268,19980792,583619739,883607257,483587989,297009180,590550377,376527249,904893673,608547856,331962191,384566355,942913534,947123745,515151923,331684112,232032592,221819778,787343215,130413893,275671245,64618546,85781677,204644766,842878028,369336714,341658546,26650729,527878065,43637946,668922229,639139597,579163402,928345190,242831137,570084116,170112254,831699350,968742004,651630168,91048507,452917992,372943302,606665580,769659258,653095905,445945313,74715739,439460995,350595754,183100962,35833475,45787574,35659307,572448567,441026592,550837946,927416083,13120378,158753551,26125338,107631940,695649373,59202619,951190355,799272798,943213081,767808856,195860654,479331130,786111496,973120184,735452679,662234466,208284932,604745272,67857896,751248697,335296486,538906952,741150188,650189429,196734987,470702869,567812955,116567355,394046262,343816063,804259064,97897184,101002658,334156343,91583645,325161560,697021366,586471526,511747802,224953019,362304723,298233741,556527553,588029737,228912764,58054068,666032721,479638989,675263132,964563649,462386999,509934327,569220085,460651076,179038754,786494628,512459127,12630831,257987338,664648154,418462102,500777764,29285610,840407148,269508279,798642891,514242819,669287917,832321535,968362383,489422545,794653792,496212418,745581052,698680009,985007593,986640688,657255170,938378790,271684922,576412035,614138049,144488312,652149553,210278717,399482046,196524082,596208891,383897735,294782684,959241643,777684800,686154167,687888248,440560365,209721823,959600863,436772908,230879840,431220209,709186392,437308968,765439490,512474541,280472027,930657520,26548609,642411115,881517879,783873221,177405095,605532902,749009301,504289275,265860190,8505354,731022085,151280044,153471422,956499070,270709879,590614388,767298665,60627712,264536289,149469489,907575575,946131379,319696422,763344966,86266226,845554057,203263255,106816239,952764832,896346462,548102877,535133977,697403204,519278360,472841373,960908080,128193477,307813071,297585361,79034888,140008681,251009292,140671916,843707329,235010927,236246311,890126086,952280850,389834024,106462680,653721535,390174783,480722853,474368881,869641220,933869601,524567473,971673393,402603426,939792713,925325018,132804154,659278672,588309928,499733779,562250758,639402357,883366394,284514562,486165221,433930385,140379614,964988444,520133308,939258314,812815339,161257042,86137295,45544474,263527286,942580874,603517953,220795629,529830083,392619023,190881243,398194131,177828064,870874968,898790219,43842009,568275473,458709491,593648260,991275033,432422300,161837959,208947100,403710266,327813037,291993902,659699400,284923155,617795022,3727663,687412553,189648848,95764913,671699261,693488895,351320057,803177576,139865376,474220568,578305504,620000227,223743424,392258749,679578240,468820508,103578234,127593407,215368784,658060907,704987180,607517411,644721801,544259616,502913155,440569183,26152585,266375204,77875885,485647027,43923336,796120575,168243045,64609236,540836781,89617308,642548624,804627358,79652595,901760784,885590586,67289371,88316954,800724203,439897758,114549499,684187229,435438503,253595041,154106034,276226289,534990064,782032107,471448075,445075610,995243428,140968404,378663535,477666380,90149177,418675616,641069116,771694212,914921384,247731378,923883110,908800206,505577260,738563637,378561204,26344459,820571483,642523724,267843973,795562510,199285060,749866799,711859687,574562979,919304787,37131829,536208847,665508104,637230759,693989470,900296056,656625520,666194234,845285213,775719403,194230282,767792805,951243180,901431347,311410240,319540781,89195234,667605617,234277491,934840694,476618367,360201169,891813014,959824458,53313536,281654690,835695011,535598000,543823792,993874189,20448214,536481595,449195026,619048631,955293872,644665912,902484839,400506815,393220665,975189204,694847078,849978971,440025280,313981274,938053793,889762757,993915847,286463758,237382096,469121336,950247031,447331735,883574295,16773211,498888533,658309279,195561540,714710604,68123790,549547157,756379990,820608026,336116557,765140584,261270100,840572849,885937456,325038947,225245717,160918003,182058717,184553426,339554371,966468213,43013260,109664116,965461969,837294482,673926459,374896687,893608335,355138529,709039904,304141856,395216426,671168208,615748032,499616221,746123946,291817184,741542795,129103853,192381059,574438319,497582405,129043757,102442013,115021762,374339101,242323105,662681062,762798418,980580820,474446815,148512687,251874754,595311607,116848509,758015057,408265276,336251963,708648514,714044847,738336997,247545960,326127125,388965870,826035247,854850978,289071011,267469191,283862300,865016758,32438569,641652085,787470841,917653054,311373541,229893516,587039860,660684712,756191052,34796496,139934181,164930130,387615762,20048312,861316747,448842227,699419672,953466215,247691682,862147646,481941817,402060002,561162457,118136462,569186487,798078552,947281901,738352528,560319109,153416685,745393474,625271511,542344411,338241835,840024304,202482109,674764013,14004317,372968168,986799595,132159399,635200122,836822063,121282053,963339361,367003220,888728854,224933062,357007060,271175681,483210059,245220494,870275033,119707225,375377745,658700384,297168668,601030089,144906622,197168925,568326127,692401505,186900998,288701148,283291809,624144645,212119778,366484910,498992761,799447448,815110265,364371255,552643818,911392538,270783592,949742536,987137675,737754293,34624487,949264266,271311705,337675653,722867038,95360326,635728304,396587274,848468246,896398626,590244042,444217296,496171401,611742012,259119844,532508108,684172491,977081278,463662244,660154109,184550095,391324667,599285618,744572582,229987217,237965036,751813672,16968884,872952405,812596555,918159323,582149949,16697819,534122209,617354455,68765365,980669384,902217341,119797452,495450578,798086058,341737918,136112873,605258802,640947223,942063857,551775698,268208087,235969865,9763918,583617434,152625150,377690141,483084976,155091366,748213010,983381206,77192083,996173520,493825473,620764038,921911728,948074054,192172174,957526694,326568716,158802900,23246546,368123328,843104460,841762023,759263913,651510856,396873553,907998726,506439906,278066166,437329184,460716088,546823300,298719637,92056412,917201518,850958420,722528219,466256055,7746324,608041232,345092664,146315731,946869001,933445170,30518564,67734891,515003524,122715629,138444035,115741303,853525332,964462428,103038580,812869913,991980912,204357324,919194760,864536212,797791452,783112496,614040676,550814276,804417127,733629923,496474944,756947314,862695932,909279507,388242232,270590514,883619918,95516555,928030613,981479375,87361317,818464150,915418191,32906628,472984538,399058885,649097308,159003255,952937021,391354016,986654722,572905441,329542689,176106520,600142254,380374475,570344736,481405795,900677132,76844445,113640234,174961331,574224931,690850332,895958127,936687863,291784439,609063008,59162065,735785952,973814616,402216667,887548005,309913214,199381792,489939823,332446022,148849116,997027919,385554102,269332803,300611167,603943578,955203638,26560823,487186717,379004994,474614559,825150197,720049716,229328088,292664440,621386800,558955858,251992514,110052912,661836091,385200136,280819626,766659184,989513244,840359627,68303699,971502211,50597105,560306557,65908536,674622455,399068634,152121998,983332802,287778620,826295023,881519351,52608545,187798547,39330395,750100319,557493508,845711608,151154995,132743794,273467845,426546849,868808179,528317600,460959850,801531573,175599325,618683921,236932324,375546058,659566535,832250796,638775383,68886193,40857645,199487564,813433350,702578053,580654297,322275679,408729064,41254765,936136355,328331886,797990877,722015203,367202878,589333206,822636573,923274668,570084587,621149636,686445242,121228339,871369299,674526335,499599326,584812404,60173385,777827836,711322339,739664204,646226726,486060508,147198230,29428705,798097712,662556689,227495859,272097335,516028318,70630046,557837174,610279282,97673210,955357644,163274236,866379874,583102303,229166415,56369978,731112023,919997745,750733666,14382317,680394432,413077445,377437835,44857720,651163712,534986900,806799420,929730901,357701262,458846243,704463189,99977562,720106922,103549040,768212098,448441018,495551090,28041576,638069358,840311241,287859172,648719004,747907266,76480902,237780850,46916210,922102007,982006240,871058485,619224283,385025533,966929408,4996142,880869014,928252758,172384490,489764234,762049767,280782729,673306562,43254156,992264521,322967240,684303374,461615489,64119758,242871651,340124027,698456160,32432978,155276847,901393640,514704355,210294339,11813806,838651559,653258139,772930788,141983184,514423484,334489725,432588214,753481063,412673321,162437530,689067441,749972232,344053353,986631543,594247055,599885949,756618040,117566018,95936921,48845446,526142268,516198786,563649546,39384289,99283700,238460730,479672307,186048491,787074486,661093642,425145384,223250944,125843393,59467700,934772370,790836871,757719292,552592956,765651173,492139978,897796132,260609230,54859367,291632269,926733661,647142032,435511594,632199164,47109732,8046813,739088569,331800444,810927747,626597630,504383133,57475374,391331033,394411278,953761665,295664747,667083542,64436265,890079988,165042185,144327098,521008121,151546046,576714076,291520435,652234190,491673100,209065885,750153450,588932353,770040642,368861072,779625267,943302398,482507073,358928463,62050475,181475728,383785758,228192841,128961013,903687045,852689930,175695741,313362698,403495426,779348901,537519884,705716095,490422805,284603719,962412584,741296415,309802625,793589110,795440751,935379047,523010180,168317909,49043878,796090417,382945745,953611874,880942237,383811164,810545335,246735910,347903226,327352680,536164390,590025401,16690807,797168008,136100465,932373971,30271203,71704527,647246496,284164783,339406597,518668746,791611640,265085089,408316797,724476292,236726966,814588464,99733527,955537042,17696311,272750207,385597482,552635201,871683117,133566779,340384316,605042752,880018402,799135856,441218512,204852567,816634525,114926381,969627630,697254033,595953354,684329147,928057325,484583856,709702929,414922771,946269425,399808612,286399705,63988208,871059952,840237769,240347981,211152345,460926018,938749136,507108156,243017463,442599701,989817346,29687003,221814094,170195289,192052084,475266546,813375930,236375916,9131309,443256674,353886617,272802150,552086880,737835996,673856003,334290522,197865641,717868721,368793462,918920054,56350793,330322158,542104678,276149042,750414632,856194000,493396031,727878264,284828764,705950673,439803601,816082558,322418489,439534847,233332840,855530533,764540369,537397470,979231862,387283007,582553347,484385437,977117275,794173780,55089732,483408208,193027371,371213227,176672374,150984024,855577247,104987241,796342302,320765419,710118406,408929401,591458972,405160196,954913146,71494647,918716856,845979253,65455242,220271841,32983938,465087575,157575446,469341896,912782650,800263393,593562906,629854682,919315917,595191790,781213279,835171332,522684290,917881116,577283484,108026440,49248795,154522980,825612580,42477382,724069205,682925160,578755581,888955810,176703285,568297059,820065656,513771618,365690654,626936437,727365161,923693041,534075886,402316618,996347562,263388780,314209253,651822496,39935859,698341212,647527230,657933817,752806521,337764599,816467891,328802946,632058097,947275271,272689779,83493632,499359688,240234861,939053573,751612092,406565161,777423058,102246284,906524160,265473212,939133350,971645733,193177261,825133701,436645036,224917053,661626809,657131127,980661112,518535689,840922511,850609415,550555356,39044372,748096831,63848335,401975590,890800569,841849738,251742962,866309981,288076889,774382403,354764589,271356597,690552883,664138129,394825348,436982443,676903301,105536203,635955370,732182331,280777810,445370792,769501225,874409419,578908341,490076504,301886613,751446741,523455961,315404455,542002940,857855064,570519576,302593033,430415670,127063495,195804984,846547460,842437775,195005516,515229471,210219635,293734110,696210153,823547914,547461250,618761643,627366311,305617062,93372427,685509873,129974960,403684077,41482068,926379598,74755356,141612454,543389579,37084104,160725076,756217130,857664789,300877125,595117888,864008559,146620423,533871238,114825206,128821201,84338862,709629968,712566105,638827741,669488111,153166755,929372707,78284483,838654442,867727485,926580916,249052112,367531646,935750999,212805209,910277569,297458462,553263108,397689055,943896178,596602454,119106252,630507055,143156986,338261900,369167858,948393869,662418775,860768185,860083422,976427223,357576087,684618284,585415708,344070755,969447838,184158479,182547822,96794568,580305516,151859082,900360699,779450665,854546978,314016744,913259418,629734435,692927800,337976410,22209304,221523843,973906266,16626810,790065280,751967023,145243431,259477643,839727739,323547713,304716660,285331525,537659480,332339876,591821566,67872368,96396675,612399888,436361052,925446393,923863638,565311125,876867499,241180857,332779143,573063828,2568230,900938739,108905670,794364380,658578186,884926336,318376460,931513995,702017887,996750779,610947743,363325024,284242724,93723982,65271233,446286552,96043875,24762178,399965147,299930784,103266536,745597599,634583666,901400309,748254615,955354518,805079275,295790506,106384518,569452976,105083627,
};

int main(){
	rd_init();
	ulong n=rd()>>1;
	ulong z;
	if(rp[1]=='('){
		z=nazo[n>>6];
		ulong s=n&~63;
		ulong a=1;
		ulong b=1;
		reps(i,s,n){
			a=a*(i*2+1)%MD;
			b=b*(i*2+2)%MD;
		}
		z=z*a%MD;
		z=z*b%MD;
		ulong e=s+64;
		ulong c=1;
		reps(i,n,e){
			c=c*(i+1)%MD;
		}
		z=z*c%MD;
		z=z*c%MD;
	}else{
		z=1;
		ulong a=2;
		while(n){
			if(n&1){
				z=z*a%MD;
			}
			a=a*a%MD;
			n>>=1;
		}
	}
	wt1(z);
	_exit(0);
}