#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) ({unsigned _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 MD 998244353 unsigned const fac64[]={1,286471552,833304363,16682239,660632282,824428132,615755686,279948744,998047254,577254938,639703568,572853506,453670701,629396128,794183641,61974242,941747501,480151790,412973089,968567343,772656801,743396762,36327821,371689938,893229936,756394555,328334944,145131349,893518880,873657491,564833604,82259332,776540593,305816873,688873642,894897875,726993833,572606552,932983970,250434440,128216278,55223843,649554864,121812779,871562632,901648783,761498663,984972809,210672823,177315120,743270971,380829872,464445908,841557476,175573687,96471593,833947050,115188050,357823271,41089567,172803714,493490299,350866487,444996931,690071003,424125128,864179410,671646777,288856201,732280172,929601910,511656153,106778689,122018287,313992114,700958286,466421725,988937716,757663653,296386874,46617525,254372667,347362600,526215428,166862154,852608574,693078209,73914089,144244571,37322323,882408898,773116053,983464882,842730218,574749332,348698430,213768760,543519061,741463662,451494118,890142251,481649929,202262961,114957911,658405368,172047205,737717514,330232654,410107025,763841168,690309,128699609,693968959,781729700,341886645,967224679,390564572,800882184,396400177,815308976,792789611,531113546,568189311,432487119,896995063,230436398,457044531,507966530,80489582,893052445,402490933,493079297,716053903,79547563,234035031,449468705,701594340,795475190,607706743,983035792,717580013,956156670,430127488,784372923,706932617,446414720,283846067,565228323,745989638,142349482,143778807,933799365,110865259,748337613,791055851,737417668,462638582,569620620,39061954,331242195,794151417,822429605,152451405,997289951,642848541,22179716,252219955,151557983,372254667,121355782,386610321,682674336,907605006,429488758,954675005,125755877,465499254,816342965,577331041,882650541,33190716,14893808,940376360,529993398,493881726,787943362,78238969,294449915,281915241,445189603,525399348,36037,696674125,746058434,732119047,979731058,404203922,514190403,293469198,563065515,903339290,439577085,262058298,522014088,702651176,593092132,185617355,212199986,679081391,752825866,397318861,568730161,456285045,189911244,995214301,347468644,251192546,663044694,379010026,360551322,187135021,715311814,745508031,4427124,691448896,384743125,176805032,860882887,704014229,700644793,126954088,346521898,855356143,775707659,208223105,757592908,154176644,593324656,502834844,627011393,713797428,856719712,431045418,952654365,553507580,455064674,940384666,308514873,516268909,443267457,311994785,874195032,226456217,372511745,240690798,838064934,275558954,9744227,835896059,568353730,23745510,767555896,753187941,28487332,193192626,827468616,984077911,912446680,360733089,126168594,412556172,67287558,609927147,366455100,721934275,689147432,84672440,263826579,769834809,323067536,805529589,652936665,321838643,757284899,269450156,794045257,257906422,84459012,557311239,637356654,88566463,24859679,609474687,801284636,271312438,950609968,147254629,989271103,392425552,100782729,837461266,570275500,587089102,546533826,831274938,228620411,866637186,224386618,494263987,129798965,350415814,608302314,526295537,329735599,142459893,170123101,85525688,62286044,327184650,462896104,893291440,300086752,402569553,685191019,642211999,791707887,195685559,584554744,847533864,57994953,242231840,516806656,197756513,548379412,31824637,88295169,167105676,861438723,353747895,750990917,509639222,476314598,802056356,957747423,853727910,405464247,831600522,719269962,353598971,153987731,978561833,613877364,415665360,661973355,499395536,866666290,240171711,683586985,39982516,129406976,336169897,396710432,449042465,945983173,972199040,419357392,95933222,364793283,192812445,147125772,107342543,891764455,904039668,948525576,245279983,841841596,772419561,848219486,199239745,885903784,556945780,175694455,219098611,401024718,680052439,497163200,532712922,295926629,455558559,82700493,498333175,288803520,759659037,95554736,617923166,668886273,382448388,865624190,186268782,779684855,557094195,166482180,708854839,882699893,41795586,73836962,578610237,849941771,78652428,735896800,277858531,518421142,802232933,124742621,12984187,859830510,688128904,491060329,747919798,561715787,535817571,111228750,195056574,99696834,789300172,837326830,818828332,647300884,787058383,828371552,785210793,433165679,792752264,631979618,198791639,83680428,872884844,772269049,92731264,796048295,29229932,845897647,215288339,966776813,625337189,968855042,162351690,67794897,192208002,754382331,305789340,328466455,395648089,329328178,556930505,156166520,848402600,993365018,935841200,360705744,739452219,218318523,82719354,322355528,847923750,416647370,88346797,723857745,427973031,97282833,352294754,56783048,971216492,93069728,333609382,214149090,668226544,16773241,945190338,770031841,28263099,946398356,72555329,290052831,626346706,990039270,132024451,250431434,735586809,187550525,933240006,951805671,444078714,516921601,294810364,461273576,728717984,245174077,697493119,106569525,89776222,316382541,317167980,905399910,634069136,89406200,554517592,167376073,975123855,238473781,286593746,47822684,491684840,223760288,704831482,997798204,349238907,190773727,175781962,135521874,722183454,679541614,517425508,64411197,385800478,829081565,962437544,394326817,336918851,893324199,142048283,177539866,987517815,823958372,246214261,877515210,441983058,303493758,887149558,902316178,371510416,742970455,537538243,811366569,633366503,728439795,774835317,376726000,7662316,738987995,929755976,481353447,908602335,890790621,710650969,299972217,225756512,1123237,233309687,723611679,758306641,703993128,806938998,3736816,681384044,426546861,406778759,654837121,73559959,8445925,95933634,991642675,119394064,455170440,36674428,821611357,296930470,691176075,799843213,24210065,497211282,753535692,561308294,4448633,693648538,552382214,409781810,392637714,199343329,250516667,91410189,272705805,699020919,271985683,788392301,450343760,427321092,378957320,889678732,423712942,594112456,488530659,276309710,606612706,775014788,806372146,562266189,122560987,910172402,531172979,272734405,616159775,863236949,521134586,292630666,165851648,363766453,708637588,301492979,618557620,466975660,166095606,263791700,858567397,905192639,705983787,119948055,223646159,417246105,664906921,233939875,317363896,294989394,648302037,902709870,107097727,662846858,685051954,440929533,82318356,792232676,597355306,361198484,318236219,638556471,910001360,519681460,213255956,637810117,673410642,959561671,458642408,507141122,615892072,366582762,586309939,535935445,880915163,504375121,941127894,205822007,424853746,285767583,704111062,395546350,628071760,388590899,275614214,887673597,440977288,803924648,138200779,410591335,456218397,746378863,703525335,39811295,238038149,208577321,84527253,919760763,347128301,808844251,551416082,31435587,540161309,9410542,878490035,810793504,156064468,112008789,772763830,194737610,383978291,273983909,946721565,610660887,56571336,41965286,378827714,854237285,151061316,375735977,364130613,856039476,530026034,790674508,607474102,78921088,277691725,152031918,602518375,593698614,471067543,142859121,295094767,774791943,90495572,552760801,275698715,765650325,532162794,581095459,770867967,29405696,188781537,96553614,528866111,501394000,71144894,610671891,880758487,270295648,316634705,570927004,205177841,702144816,641979858,416335707,949649257,322647586,967049147,724929380,228186121,668190389,25236287,186976237,862300086,703037768,768910251,249454012,667710249,374640872,917706268,793389793,923799383,673099235,419064956,85471918,502156950,828575570,117997930,612557047,638605387,409785103,589718422,617232885,795564478,197994359,126077188,991001339,360920101,471196104,892142679,36195913,331714831,427008196,60577439,836953803,254314951,622431830,415464295,943133006,692084646,320889851,335036192,935325182,331853767,669808842,368168954,253241428,507396542,618129319,242480018,196912210,821261134,508037758,243123092,560015257,141388878,883115987,18457263,116862314,110693708,649186112,339830785,360458601,511121854,15572513,841002769,350894356,162897432,171226766,270082191,351884425,622370432,151590670,598046531,28456196,147529084,779823636,206209491,89048304,85165177,36410173,115056660,471313270,549549359,351533523,411127887,892873128,954841130,245098264,413755959,409013688,253835086,820620751,938132675,423468103,626001327,355993026,151787967,42136810,996799228,654400734,857174302,590505909,361603191,286989423,755889536,54560148,602215425,567832112,449433592,659621753,493252575,530820121,274955954,263118207,716673695,525245021,100183326,807872067,602283652,729221238,678462491,839784479,16400401,839742886,306394237,76363718,199682956,625139720,535722672,286400316,60396366,243478603,914579851,345748553,826512296,511226407,644719050,338404883,875800931,382861991,27904434,87428315,877396499,650294959,605065787,35605009,190687654,88815737,636079005,876800343,448948416,874957813,583958857,458264071,323511891,362237232,32239143,984386252,55932580,945396153,181932924,526649590,328631710,986363786,700211955,109457012,735948999,979489918,362786843,17695476,508314367,304590266,685666129,232867463,288558409,85846478,289224975,867954947,407600403,602458417,408399344,600462519,160063744,228248737,984944675,162057374,497031920,784423347,323593469,490527645,219715853,422778818,348590112,195678676,819647279,757899527,113999820,817599348,703461396,453190470,117026188,776595907,972849117,177727718,995900190,761707589,507344472,101898771,459336830,84382203,211555242,650331195,238096036,158395821,900241093,223927796,100502906,868569575,877481013,37159193,390270311,544143470,386488231,576361209,880338463,342883032,620757950,368017017,397017708,287424543,662303528,852989243,252795901,739020347,324400426,980843223,334857060,353721093,776211334,650534250,944528374,854973120,677370271,838941092,563054656,171367935,883612301,50287712,960579110,25821417,783457681,587776631,492803858,349674932,840775629,57485441,998093292,168852944,356716773,893326188,195432705,892349312,192495369,509033048,514746791,270362229,317861018,502953510,484039959,543154548,266895219,105279578,387408579,605429941,309141258,804181570,390995440,147239955,956571089,243625084,242485391,372446322,345636578,54446859,207520788,670319618,982554153,939503743,869498158,537861921,905270883,533775515,808896884,750783617,663833010,40159580,779375473,545278847,121058238,825179542,692873933,67843887,749453007,35456043,959378826,901120568,304988312,875084334,985349834,704928730,200247030,655302994,816587716,820696539,518051512,585608990,807658326,558165174,740294965,491478238,253699617,588206869,639396704,572908377,767337456,514973562,194481689,829942035,7277940,361020153,733521623,752249314,946091676,130627544,172833072,904792371,464361307,429130458,328435813,897732470,784211455,776968250,86085002,299277458,88109811,422352754,658966188,449961479,680297407,840294252,500305121,668030239,105056817,111119806,535813961,483746526,151833762,427671629,957476143,86622874,212553786,705608384,726045192,157022628,371944521,791743871,132729789,357378813,759341207,296643356,994406989,132807491,689470007,267377408,261950123,109276119,119526993,221316006,657637699,839226536,909146263,935157849,37720069,522443763,328461187,889966700,196914218,428203157,769680532,133909913,768226823,75894103,260676348,285648044,662346004,947896940,942321689,685564027,344060063,456704025,402530105,55154740,881723400,831870080,89802486,293425487,719319560,424113548,82083469,283105885,679663322,333210749,110671221,447210999,189221062,261210723,941540212,106056475,942528372,191486187,573740295,27774089,57256090,567421291,679497225,492000161,478718334,559290254,943624300,932447181,369552746,781171669,263159608,133554956,485110950,500608167,753005417,45801002,916333952,676588086,101603866,208063299,995351408,409258328,81495462,159754318,982874087,735034107,219530184,166709838,638767167,558583657,356022670,728021088,329791043,620367716,54400004,159355472,306028676,153516815,722999605,128432866,278573443,262968767,200971801,918184000,914017489,218305393,598986302,392074402,130587033,815463188,322582227,896014788,543555223,716432580,17655347,720270336,623833900,175794174,703823376,931565121,736859011,706308290,734538241,447978613,449227396,44143218,129527007,763254266,630762653,136819710,311459557,947796254,273845103,947822434,139736667,188424601,29480162,666152946,133100202,514409754,487056800,810930880,430284909,210582481,120570349,645357588,452787069,542068302,357177013,3090761,125718514,478790044,704873566,618587521,343382206,94230363,341817457,499782,589646693,296750386,517081938,173452645,922965596,117498938,772533027,774417057,505966774,232883513,726865615,694314651,310362194,477797540,986645589,416513770,560602495,174292690,649078412,758445942,740662152,354911034,933334372,176503116,113553032,728450910,403250925,893903706,639035980,335884626,551207560,59750787,507555412,478600316,10261313,875246426,761412857,480380030,521928474,551603116,174774350,524477732,866167280,236868821,314142649,95462985,106420747,280879191,142061618,982869783,243552037,317788254,766662278,176274759,234685589,787038454,639619841,853650250,657089927,265880620,862302741,735731646,983764839,113328955,926687457,776524873,721700318,288677549,465208211,312646570,986164545,619800552,86324758,528881106,911388650,910456692,469012352,620302954,811887670,910641127,421313269,609983783,693399707,761667398,81189685,216939780,10344563,775911695,163064043,366100988,904154863,829097186,601788534,238834815,616791419,542089438,381792319,977085124,394369447,935991314,908205661,398648898,473781155,320999397,788824132,982305958,602375066,707521469,778335882,263938801,720070615,873391271,322417762,89261916,680332035,230520537,75214391,349352841,114686480,943138817,256851841,935149671,679834567,58493165,94032360,34798487,186193969,49111081,195889571,919970664,811362891,203069278,227085504,779227920,722830646,163244519,887479277,75304122,933974523,771692676,244967881,745062009,883339125,422655771,526765000,43882372,807155300,718936336,703089143,884899753,754246379,986251912,326834166,533347647,835494171,62989663,452214061,233038929,865016957,749741439,376503367,310799637,46835111,612647040,16584092,763407535,418678500,810314808,455502215,560490087,992842945,272221068,705376404,717872468,230241606,838916518,649647824,616994025,348819346,301057324,665709696,552549322,260496503,827345410,884655075,597592827,531804553,607804784,414568800,765414633,671362302,825928836,413647459,947489953,493360125,915134151,682866639,434373855,681203105,869351660,305286435,399543711,911073130,12701348,475180561,527717450,724815727,422316600,481847515,105907025,578531593,450639547,750685814,102767932,228662828,64927239,558033269,330269896,18055620,617082181,554650656,577026905,811226161,445140078,173537525,77818708,747984484,373975693,549382142,130342298,917855574,43649459,981227538,569008355,863759168,137535234,720724874,830817878,75385311,135792920,246332743,70847234,621232052,768369869,709843458,594640690,168971337,967385014,366047718,369493725,692342142,162679289,590719043,486553556,31808658,796315921,546332989,502878031,735192073,200840560,993049025,6867048,141123546,272402289,893102984,95676989,194399376,496321260,869356097,311574227,153584517,334523653,406554081,21964598,804094035,268334882,592398330,917434845,980324750,346208520,9401356,346188007,970348060,721621377,377214839,986679467,330911389,505750213,181171364,510716609,129732271,30197571,787004973,434430412,285973148,433120538,154867816,288406188,279347341,145800914,155999295,677148559,973890126,745454889,559376030,635251199,215502139,147846900,272613132,407144104,903930765,810166271,749208142,388917138,927001291,696129640,680344955,693044164,677425838,284439669,748806361,246090834,322153477,258335161,899219653,358069373,680766466,878017124,266239726,860564156,951044886,827540844,781339297,678186310,288412884,264422227,787236285,757943100,479298950,971883134,277082297,718877125,800683090,896463581,590977114,977374747,388537920,796870911,593606265,48430310,917517331,488144299,739826408,651175618,174412960,576164579,923774746,100822180,993211403,249958732,934170518,537374795,938959703,583795941,877120737,854393224,71542309,264594887,501655537,841091105,852565013,679162063,43382883,510058232,69127126,751182048,971561004,202094598,883318873,849587474,303162746,394433324,33867289,332021570,194592920,512574572,67716724,112547659,757065618,284965143,297850296,950507329,67155376,164197917,914417379,413933258,383467020,442818164,121129830,256723915,784684692,778824024,25540191,683806567,99106373,680345933,382445947,27440215,8903406,170065058,496635723,464495434,841223372,8174354,298855761,768304408,956454700,749452707,696770269,75881752,917444394,175598108,839434650,484691018,663119841,713082650,518418365,697986031,502736239,421843956,577234241,506153085,545158543,61830166,164367128,55819690,365971830,624825292,427267366,158106232,421013925,395409737,198776239,253556416,1620613,216037926,231594238,533770970,14413319,203570639,326433014,349572685,878287091,413478625,501023672,499362242,763829581,500621017,2091335,572373670,388881716,798398930,886868665,929732704,47261207,983884556,492265759,966821658,736521,592430373,120651708,790052392,989122408,49933947,718219832,733265923,830610342,578953612,219108753,471614028,477598732,153093088,136578120,669287065,17011614,724533551,194976365,157503015,313125308,925593363,887614381,2562202,176948560,574625299,420205939,243021423,659062176,669175002,905471063,864812543,338576917,197397755,6466919,746610101,581095837,129879513,712775735,852411332,78500879,790295362,797366720,36822049,614890047,332804847,300553019,83374616,370250540,281113515,386066706,807036282,388778340,912799082,433457841,838644885,316901143,273289828,314692592,195608626,939889859,78545181,242198902,373807994,48266279,930586987,27703516,137190747,736545684,632216364,699717863,696061079,379533295,533392578,748034532,792193516,474783231,665545727,383797762,158870233,310694098,544296986,820683857,403244445,973620634,186809265,589329828,255261639,415280448,807548105,567017590,215245367,646867951,553877235,868180477,310297943,762541618,605370907,163594708,650614134,523576497,801934671,34294863,118598961,328479887,17314731,861684268,588445499,273110649,660330077,643265844,263271699,799993442,471293923,942957425,210451126,962323151,597575970,71984493,26732492,880279785,743841127,246847834,10232161,418057225,198082544,590070412,661538152,217278856,959895711,665761092,812929775,551012694,431008506,91234432,205311624,127861237,441913554,521439187,974583034,722352956,752492230,129246395,910623876,939400345,693375680,168657889,965301472,578163357,486520227,661407912,317018242,571426068,521808008,823768832,843169718,649269329,446050690,140711159,937976859,231172880,887283652,769344404,197681567,866133814,230522693,614996290,677826221,464395700,882945225,788958768,33517339,545769072,89309255,348661238,968613027,608378897,572996072,464244944,172264065,756799393,713096401,768466180,759680328,812788561,291358368,176787170,744867256,314361369,113504955,455399748,212516562,4620876,234163831,2638268,553790070,722450151,697710598,518868905,291485458,297401592,188968196,635854751,422042779,678327349,756841058,559168769,525074347,678714564,989020571,569113348,791267689,509716023,867507307,770470559,423078903,974583142,683167407,721370131,971678608,320477615,339608094,278461445,528460054,32202417,844483723,83648072,84332458,770416892,641015611,962977389,67099601,448928607,432879693,219123613,929209828,297242909,678761464,417973457,291709749,877375472,305246885,305823130,148997125,808374857,907524713,668844337,135247374,833480475,759645822,14745227,740055526,863811795,138688972,858728875,165024031,191500690,587907345,975598276,525113773,530979713,966551774,836785351,813028581,53385630,277638769,339976350,129980885,691447440,651309423,948831338,578372491,122971263,804686832,391876484,664852026,500144462,780560250,138065543,496821381,93879039,355049725,74837055,404829672,264511849,72751850,800494761,952118131,669260660,312612755,64231601,803777516,206553591,27034534,548810615,380948712,749082940,859115776,640150180,225807005,866470799,17274975,90058568,324220863,525822022,861694996,553350094,374835656,439033168,850153718,147142188,178675515,792945774,850662254,832654430,528205456,425880714,164957117,254691898,314100553,491800648,910342402,545650456,174817754,244847182,402763588,60600682,137876639,446439366,80241474,221968195,240143253,978735296,926841231,130278070,103690150,787797603,421131611,339950065,742620942,342469172,547492392,573682848,751234021,494203990,492329383,334506010,706174821,195071193,264974381,416610060,503372884,577680252,662369153,180317372,408591894,315226015,704378551,38664811,450234389,483944654,824584291,382429279,263068586,832804488,963488722,3796654,89309656,526614192,74085122,913645270,385714021,453142334,743380790,38214502,503007609,551576967,765717385,941416466,794757329,247165186,116422220,622870862,425095671,973842478,503450170,416498202,948738769,730169086,645801995,262503761,287858136,270038191,935386654,468148268,221639463,737478781,208754090,909142343,978077665,416572140,289871637,386384615,316811143,608560524,927263656,428143440,925798480,691471239,887594807,131778001,240967815,201675789,347177587,70363038,31960501,983311226,125540428,136310792,812007457,963880149,879647087,746153561,199303090,917193495,320208571,158898896,20047837,607491480,254443093,270512948,623393730,737055201,334911111,727603022,145967205,952468769,353024820,501181001,430171478,541030831,451530625,619131324,331134934,48454068,717336017,336791014,298173968,200485135,336499547,90495732,730706454,9912190,734231188,382249982,319604168,617135043,986176024,701734960,127470054,439206443,421976602,874860634,244196708,985974193,469299930,815507387,88253188,190041174,678550190,455102513,836295741,523483360,480506497,475199957,793695956,392087841,516889194,565272354,419931769,830585748,17683315,784322601,447256842,169426091,966679630,795886489,308604283,662162548,752962159,600225823,210565051,139907545,897603219,57324776,22938628,421669883,635906629,930074684,859253926,683839400,218138286,71586216,986893231,884564897,908764670,978191147,959206504,44449756,182850359,784966058,953065442,191882557,830702870,541392603,345792201,635772503,864306267,361436563,575203033,730394880,864397080,232045343,138448490,791993882,811333692,26389231,876154450,886861624,207196033,29271181,272311454,843829609,913578976,649626638,47768411,560484039,575913746,790868237,667121261,484260749,161818201,727912837,271134179,279440108,542178756,350047186,397577193,490164365,191351580,26498720,724764194,178752204,155420866,155660615,136048183,302397965,80243504,249037524,514833159,245245872,990273470,472092267,214900497,765962815,957229199,702652281,213336866,151305428,14363964,742809758,226620404,209446648,215138174,10815859,831549299,670305418,121490821,474609794,71435121,139425987,125854672,285236359,630828794,10493305,595589904,610027658,692730832,264922192,66343515,993304743,78941441,928980547,186558661,827529798,431050343,567771297,23540743,241616012,109396764,938389939,82727711,68700623,887464126,691672457,953490157,705206240,413794494,106892271,935487757,911618216,625077081,964133353,245238790,432612936,19517404,891227245,205049005,68221130,715216840,426093137,460353518,773255195,29547188,445313484,717288331,399855526,127529996,527981251,796069773,313344279,996475736,448992973,456103432,691489059,786895056,688082588,459640035,267964144,974607917,197833451,35503757,244905002,190084139,792893496,526284700,466425967,474206026,882301184,38643750,905768057,680299255,684898273,592938206,986470743,212383939,747075995,214466118,414409914,934447964,28336345,402982382,560163713,30980638,961899257,332968289,227816810,592465564,670376041,950897322,900090952,692376203,466811001,502282985,890457799,786955038,447256878,936530984,290121172,174695016,249960474,25102999,679989015,104271019,919460625,427755998,748763753,190885770,208670885,309726754,752249280,149449439,825102236,982333407,766671351,947882308,863451761,103478451,540239941,241786040,933573640,877452822,917907204,537787152,391371355,440837566,165278384,374870012,501832436,109133968,553785456,331560543,957413809,210409087,995975194,302567286,124027993,899319305,134028254,777852406,425312517,19990946,183249890,386977829,433261920,212788810,993697482,59592917,614822218,32216712,483307916,781777622,611139865,632791607,315016614,888916009,471875419,630379810,726772976,47306892,243009674,246388713,571876409,76352747,438717910,35253777,227364536,695362768,913545900,623972602,13447900,732528470,927871481,658802148,176014777,74502360,290546382,777534208,965301969,461501935,230214550,815114743,714835268,267443112,496874493,871536921,315868384,21874704,950948965,722182130,241670683,804242323,529466491,752423345,673111954,449264785,34784612,136316318,352061429,60985765,823907225,69835606,838698588,484430295,362502323,755794926,419148986,519299887,987877714,815297941,969024609,837080840,822544123,125214215,310080077,733684226,651932351,933437062,641666373,346928022,563136406,760097748,695275389,456798938,231676078,603550467,816884706,675243412,461566245,390399928,71815326,937002588,107574544,291565964,56385324,215246279,937289945,961995728,88687869,54866207,668623320,808820787,984965322,164333408,19120001,558892469,976427415,298149860,590093454,908874063,737339743,570609321,259467290,761666499,650907887,356505249,927083578,816356874,130620123,518511913,807432198,310655589,516502720,170166008,885138009,611113292,670478368,169537764,751145396,486729845,859638073,912208287,302646401,119772774,219880658,374437729,12011805,552018058,518296278,805749567,118297833,711616773,282236564,796451542,516666021,173482991,600531884,511842254,509777763,79965717,417938802,525704749,201848030,81124280,246782605,79282620,971932460,190126775,794048026,957070684,862569567,85424340,6474301,642083545,402911370,557095026,67303143,45474999,715918923,83728117,8774384,437665466,829760151,848327214,541190956,907834199,972184583,720355563,661420477,711298674,699370867,862557727,948194838,17101484,887127995,929873543,843483459,386653062,813745573,237221632,690446548,707223022,122284839,553015781,79618410,496876894,108784765,512396281,704967588,720933961,230019812,187895152,34344961,754588014,971284635,434896137,544695918,244306550,747186746,67023877,692730195,778448011,221067758,304946752,811071011,447725633,262162440,652993411,396628047,265310082,416858403,116428975,457047546,924365978,808216132,426424914,565898980,733319772,874737039,324241704,207125478,764839449,225066879,874571452,19329309,81266867,449686993,113603122,544911673,190359531,663424552,725867973,293994880,354822109,782801900,681211349,745425299,727187198,590288222,642998670,341303288,109466639,324153419,75574659,45443167,354501262,655203671,977739842,632362034,199347607,906868010,450084648,976906404,464471853,925144131,79685201,524630414,595236940,885526969,137349344,309695167,134595183,756099353,944715854,601517572,498412534,573052695,654228421,963868950,30428498,54923690,172738178,610772085,591251736,222105337,488717424,259237535,144813786,120404565,857064427,384714064,718550908,88088978,118456934,470356590,626073824,65508136,919921121,552732459,755288980,260359054,441889513,815815690,529435229,459838715,758275201,625276264,848063827,992278647,843967355,323438245,28348993,913885238,29155860,421234517,912652888,322275892,249424637,761997175,375843958,287966054,852358429,641742258,807076793,809494156,96805707,856037087,782737062,266683821,722525003,84386786,460141120,500711545,17926143,842125686,740203267,783627997,188562356,653668060,977810082,191703568,786651955,745721652,766557826,25025364,224283764,451191191,759221877,320142631,357019540,277439777,174475456,27862915,128216318,682014536,733620925,244024135,724002520,252537515,25869296,199313734,427952339,34343622,825572784,613936589,982917025,145590477,225590981,932017275,678091909,5341390,872693296,556082881,54823948,627827556,59638889,230642583,226620743,658819841,18194464,304158967,257611941,984513388,400812145,820780431,625453443,554908903,492000265,838925499,152239436,475763932,900381884,430729444,528054672,289342399,368427783,921726507,925346721,330976891,288175789,158009513,390423721,193685417,516951878,23147477,696676198,342356775,987470025,924631757,833055671,221595762,571463817,372183283,124216397,354848669,617854032,761423117,503941194,990420728,641477977,164998314,987498650,161979166,947862596,173416973,296589184,575353405,553552793,6040990,713332667,284810349,65935983,857797004,107827214,864770460,453671716,28479218,824548517,944196562,744386239,352410797,52604867,810217067,218414240,738003129,947308987,309609588,216835933,300913859,633253188,865762563,279895683,976121342,617201196,786145020,922941047,472559773,159597089,241014593,8897606,46261318,608249589,492816356,428021099,456351791,107583179,974691627,789339999,384292902,762773996,88111400,807492635,841681287,908432985,890230780,791219964,593297458,130968649,70166309,810382722,688670730,963625359,678575386,600060759,769193166,271541766,404482375,655777249,608721033,791416038,347741254,987232136,736554861,650737730,943919434,691966239,720975228,668057441,655451630,14411932,72502460,972550152,893923983,473229202,951193879,385076961,147921829,626678298,386702402,283704863,288918588,575560817,691582231,111170545,609126932,803246712,530621939,411740568,83112776,359112889,587720940,149672257,429957337,363848504,827216699,760037342,474677421,985757389,745959660,619177091,724591901,290635517,492867895,298331879,278978713,399406497,553920343,671464861,825686192,23298153,423752400,207670560,641770567,4229427,316995284,376463886,157724176,811492921,409968119,188973346,639518386,818822992,119194751,544735935,446947087,623570515,151802957,566327093,130468688,521402410,849812934,680005857,155409018,345332159,60327080,842783461,129426052,324780807,444040645,713322861,426012281,506916981,659805094,517110925,730564604,873297390,126814766,250545414,894413046,960186298,517278190,236530170,251176559,951645240,469765512,744062338,428669169,151639897,831434644,302376908,407568137,64113920,592753715,703747371,734074701,111574874,544842786,169065276,834350915,301066768,164703873,398453210,829287301,269752482,883233683,771106673,524715187,696480942,761451110,95780439,734096119,395423448,536249400,244882480,559826340,157518089,458419303,945256949,423112784,341219264,429379494,79230097,721398773,474508588,131231851,559091776,254090991,706208587,404589510,42096873,852598847,34603170,256675976,616334572,199112161,108067268,410236534,516916696,263398262,259313491,43351921,731468557,952859588,641563156,47354476,989872207,602019658,729616597,932707809,964497100,501031459,360379612,141996344,552428990,273715771,724475363,669033962,994947059,853405230,433933642,40596676,831084366,540377782,85263735,7184612,157085280,411161218,245950594,792109691,250721295,229409317,568624141,638474417,306722228,953340618,677211258,194012670,224635931,44219262,418045083,468324510,526028572,985588082,64405509,180254841,287775448,744956919,275059613,810304839,447372038,580609831,541748218,383139422,425588413,401593102,954435924,884942258,693327654,40610596,799733966,867998356,967872085,780045440,562921518,836053927,11673407,982327850,606040070,245682033,930087508,511813343,373667648,844708265,736598716,773245593,607922664,301765636,96110013,29809679,126496763,63941637,708907767,312889357,329444819,196200381,960700067,589703906,596062395,849764592,687918301,778092132,255515653,357965431,815821578,471333636,703590789,221741923,540326991,519791620,200707987,534270122,145584377,74078982,852831133,967573573,348002687,708321292,169008059,537170457,24888745,565733682,718402172,48688126,715610163,718102612,471255500,474432452,700785916,434780100,204139988,586944770,271091597,684975644,832297534,322183343,903486309,683100901,65254102,383268142,441831720,777552969,986050036,53525955,901767047,482912289,46367241,503040027,723988637,794913928,475858276,677924980,572221383,77565216,973635895,111748513,328788130,707165704,734839309,787485259,372469172,282287743,438368373,881018734,301196465,357145819,990269468,850903824,861645144,608477770,928505179,816011983,59977051,85736073,352666591,293519042,649131979,705185640,522442668,26066229,805958348,909921233,56687032,248648779,122390354,591798070,714286736,253897364,727826155,403185469,328028827,769563117,554475432,130761190,532381585,387934905,860549436,645182267,487125465,750532662,494263031,583622397,553227573,189417439,506010455,2465354,225929782,947748575,634356926,224063341,382221204,450657854,851503722,984645584,715077943,710171165,24319003,301871015,185201605,429682969,680980293,209079853,514446861,355539138,152522890,728767830,976609733,794242266,803036840,737731649,946099639,518282287,382379877,377477528,560554791,207503633,935995389,282318468,652462879,55720794,894336737,9730119,73794437,730109003,723156311,474997121,419973380,713554440,273985178,119100759,91417650,233857020,97959999,727239712,844462204,402356252,474603411,377537318,675713613,771075825,510421733,358787862,30892688,957623005,993483163,991921995,615868225,467002673,33739714,515967936,453389162,478061250,400992076,472427353,714553695,93928680,78685728,46502881,823299765,182054389,212061288,692303524,961932603,533041530,732450282,13247340,323272375,310143471,366338910,503540692,113707829,766469072,300877659,464640625,890460664,438917234,448430170,861536815,70915221,186228315,574494323,645888349,455986840,107940713,895802482,151239259,632664439,467260793,226466070,692900732,875848715,730521082,402610670,572200093,581473861,246458760,661255325,36951824,250713605,974595732,352746594,802070681,495140946,684129473,951098634,70117604,155161884,572742234,930123690,786783797,701893621,528896849,550878695,947940463,702048423,631326111,885050982,966088187,638748315,711598402,888122519,921484306,374508954,599036833,919317769,117281239,686171152,135081394,152958304,429071673,312225479,430690360,955201843,549293867,328743575,389499608,877521049,54206228,548318802,188671844,53398570,471201327,504703208,93120688,297419554,860998278,144679868,157695767,508430016,300199196,101446741,458254152,420268669,678880401,921787093,403015330,796773219,997878819,116921532,632229757,983469754,877155291,954304285,70212901,30374285,773653256,512207277,604584657,837795422,800705941,698253774,933014353,482151778,158085104,81017957,830351546,856451421,98563168,113310340,258386981,145257203,966575290,499904653,490061735,17816488,489473106,302647199,444589728,951248875,160339315,675489932,519728124,894981641,320097386,325197029,358204033,20432162,14829552,516134909,603506704,601606890,258248814,259167661,732727229,309416777,638249058,510607561,74214047,605685774,986936210,958926139,476037405,210995826,189886612,936961451,334120653,90751739,459291597,143814525,633772473,923849089,465069644,536254268,135718496,128759485,459363494,74221469,282331923,717258209,505407397,811775987,263416596,146409179,757459091,129489686,702937318,8934970,678588487,954714899,42496952,878750877,909038362,189138702,287583091,847741449,287020512,790363128,682214039,487407568,448018186,795264610,936976728,120646750,378603234,352931054,721351509,697843819,843365398,34790379,674288350,757912165,578902773,885511478,628902064,31373470,477894080,975222339,669989185,246906182,780086553,662557547,304056173,910283327,941972006,747133770,334045381,292234787,493538989,660025398,671846006,105516504,917793233,968512986,486683435,936425058,850186712,839769147,942253741,342489023,455855285,494331076,126549224,219216098,188243999,234778122,109734407,525697755,200737670,345514813,678669108,36952831,809785218,185923035,616221028,494002060,249593465,221190792,20584912,640764729,678245483,983092476,424468941,970656864,506505855,646295751,818615837,207954403,325355561,332456892,358848903,597752418,372775649,892009626,250367363,269838815,41238113,928417297,274637059,883493398,37377518,970375323,96040665,893702399,311804467,103620538,761522696,18931331,712519411,545496364,502915139,923303529,139604624,294603633,283358091,958754443,274175565,591627665,600454650,433885674,92955869,992165243,95907389,254558472,79086238,437522794,469866758,531476067,634146518,836044084,613000190,646517325,283765399,300860854,335205067,291428008,30730310,671577815,278632457,770419461,281268515,135948895,380209842,886137436,488812749,408685208,756112619,41471079,870215562,909331562,129773086,957012017,169028579,615437884,189059372,887718801,790970783,758370816,342807805,933552097,222970080,652708281,530586642,367997461,258040739,720624591,121413761,59939178,924521999,831027461,959701396,834057163,461201471,397573637,759773360,294798209,240172146,25591220,344431138,298582584,372753281,385294700,330676384,486573444,449062612,295301629,400622250,202298547,520940061,844933720,897725892,335185619,282399305,469330965,724180762,188178805,902773674,7631741,279502653,13129834,89139990,610280641,731121311,243618545,575409371,624818111,467581037,829171857,494384284,241425134,826861986,664700950,572826900,443276555,817509256,722816948,622850225,389274356,913790774,103549395,866600133,467123572,548355291,818520977,337863805,989954022,466321732,881329030,266853599,350397413,25780128,201914979,646727896,442455820,523847553,673554626,719706226,343201813,290684109,827589163,562161149,189110257,805289290,10806341,186793919,827870055,809651752,798928943,712204047,606970286,149559896,356743421,869190712,827009865,839426999,608928771,564265983,868372295,389572346,798952940,521942746,225714870,520136122,105085973,728315155,438368976,167298364,276191768,275461853,671015813,893154959,399519609,699021931,790523792,134125915,885931311,531539214,401347161,285139181,816562553,208508890,62016295,98226660,30940572,456671660,878308839,213502981,394125188,111506727,82333078,703049564,169137018,87071149,77749271,304943263,323952532,735161248,238173354,977455983,7974622,653247069,839366530,529611394,927371636,347731206,665989477,521134015,703095934,952893391,597036959,812213808,212142972,946482478,499221767,917902779,292904736,719703057,996689705,660779922,432055777,361342884,371842256,373684420,278794502,447382908,606229862,166774696,886837576,410817883,20019209,969373841,185786027,647965657,741240125,417535155,814087879,524598278,139439942,770435522,659831732,362961348,154326026,572904501,130873219,964515733,74493251,945044980,270441915,705137433,108384426,292591232,286889412,243828128,805694144,79339290,108660930,398924716,361671183,382722392,461180254,826174947,144869553,646461465,100828011,102431373,251968183,745478775,679486576,500889362,848907331,154310156,294421901,113503573,413774614,107492935,948757779,882874348,441989341,430969087,819025983,619946784,967140099,621031887,569346986,750165803,64454338,63889023,152453804,617215022,227075193,372851404,297584127,524442286,25840139,669270419,414654600,137605368,193757822,942255556,523439781,494063523,783579672,464584840,591796585,763203818,608071418,474088352,642033060,921680143,106760310,695241689,513272960,368532054,306310256,169021453,581831716,154340680,561461684,832019648,194817883,500190198,914590447,526403292,324367648,853308323,536687036,439724764,764535358,25998845,671569832,197137754,741031731,348474793,698191168,533260151,479309975,504106695,407447508,610268798,517906944,765750766,23965617,385470358,790232504,388096238,469082130,797631847,992183105,932594934,975969596,947573106,387541213,257721625,552058576,28764782,113792973,351892542,215697288,84741310,407740136,917999580,224499520,704802471,619591702,440730145,172809270,519857921,191713823,934988209,47474609,77275013,829343743,17250168,121001289,79157705,294241223,636861975,903947353,829854035,232166425,369684167,938539763,671771873,662947658,195679086,386778642,776295565,950763236,548678398,722564734,253645462,231978439,447376844,22357434,318407303,421350548,277366405,724213861,309062066,585304450,235333574,758202478,699946897,903955971,348710644,770293596,952420580,567662652,295096016,148013915,660365478,861111969,164013869,353869793,538034974,933834478,113490868,385950691,678438799,424045942,935546725,641835865,493040292,200611226,887407942,336101124,556904928,888069617,783314407,296208507,576645721,684733182,52732972,703740000,912961155,967614643,140632356,914704190,156925988,624517140,692115133,528015664,948310514,697502085,188897319,935644309,723670398,182654657,307740851,966684774,703869523,702812965,15803306,8483364,284564845,844390032,540652542,570900523,600521382,798959158,411783414,782324144,36710053,68786554,637231076,546362027,406437278,516972950,912218557,44733041,864166011,498681706,444202741,864567370,775971822,344259376,733041186,102859525,32013745,735475800,775662845,298705630,840976686,183919573,643773370,326621610,230049709,352727892,356992173,522468112,5784240,476383952,524249737,280380235,309261371,707936084,2395750,676952658,295903936,271035639,331714058,744928746,949661689,282674405,316867673,275399261,334735591,482644143,540358307,103210970,184787710,669474406,316877835,326449356,394627230,836396799,787630439,879903059,765531193,47140072,898017500,790204027,194833371,180493239,238518920,5640257,462857762,494010898,487569737,843917452,266836484,964628638,675803671,485223207,40235433,726019153,209842121,802347636,704379752,975324931,681931274,653367415,436644798,67856502,576081777,242409430,779379422,240081720,282710053,216819507,797946610,488788841,106987925,828388324,417411704,489529799,977393329,440312331,44297255,938711691,670108534,587833706,896375260,957598850,933661334,194308788,930075412,919728606,462344737,483680301,621700788,817841564,311802469,480891098,275409513,804241914,707544419,40469219,796309564,701374692,902426894,478935956,138118845,452870537,852358674,862686986,186177250,28210514,645041236,926156551,795841922,708147400,777164395,210585234,856027735,650896876,333846842,458095010,323040305,325029050,484578174,802663428,684750347,575434367,207474167,156380143,169159943,430772577,404757817,354879640,968070089,592510558,442999952,91808759,820384085,681128761,419745595,134677404,715950821,325224960,139271534,34449461,154105003,933040559,990899180,771230526,935744467,969049241,52012091,924761076,565613158,824989522,9777595,65242117,160997998,485631542,621077968,745283489,373708171,556501496,961445152,34097422,525824940,960164957,636364825,323810837,690390938,6879306,338082888,409256468,182976421,456328825,282785648,394344892,908738672,132675267,964709388,102287772,230172998,816013602,934882311,778831289,322836463,348559874,844258517,516769142,65321975,242728778,937498879,751162992,784154518,806000560,373000996,902362543,483853100,355592698,560123341,274096619,400467648,404485561,959427339,753315607,228627460,34313568,879629688,534675304,889434848,324600601,446389559,722263693,104964111,585976258,532018638,226374269,547645246,372799202,661888699,350468654,641463459,729946527,695301520,157598024,381467944,117885242,225744952,814944322,157110489,769717709,389374174,743636055,900627381,141534367,90812716,150558142,603697596,930092702,215079980,551608905,595851024,714944268,427311446,451297925,312728634,299606714,602595474,247999633,697559952,869187476,557369278,745331442,597697953,854635771,582132277,439685923,870425627,710849349,173365376,902863475,945005324,617659144,90299795,526916950,675225271,444995258,625262204,218626676,756694571,351286727,867328588,195800573,105930990,528266432,784793994,817029670,344398837,301301141,474768956,597126085,641603520,877803046,94095287,908892091,108575395,938773773,272413243,75175666,795793146,14397091,632085715,905023960,9007927,476682638,348201405,560742841,699126375,440372325,693984338,72474869,539566875,501432667,151014617,104668750,498659539,890617550,489600993,555424886,184588454,399426846,859451650,740965252,759714205,305058303,450047702,725063859,450940487,741415773,932020259,190031589,827115231,790008363,119493105,272662632,340594361,21589023,578980025,113201611,193055172,317969101,241803936,46920107,463388859,161173637,56175256,754165932,566012269,207298152,334104244,394766353,343133531,988103910,427113379,996938352,682724133,789572350,734198537,14702847,413834932,737496044,556185754,958677869,677540903,580627090,854364369,666370092,460577082,732574605,442999532,960255416,363627308,109055493,495146465,485864063,686090289,533883024,758893596,294098905,819980793,130116863,250219210,206219158,96683740,808227955,372473964,742411584,295901410,674695288,398823129,544116773,224604654,471381953,623155373,759743729,318936345,562615949,739716607,15110235,113976370,57772219,268558162,938900082,946978215,510124217,218419345,456953094,248445308,640704070,642844353,162584273,365867522,172766109,31469430,976379739,341978257,740690241,957026127,698023604,762767638,66508640,965225204,16705517,211183998,580316388,699484796,37703807,446540191,427999170,817487749,965535222,325042398,261209299,120665334,907784589,193776485,636748100,807258940,461931208,576284811,335350137,940485596,695402971,209429109,702262927,223761079,935252937,767019122,291434539,216112378,896913402,314696994,160790316,548302034,641611836,918044456,12354937,221893813,407042320,744471444,150622978,353393183,650991646,827891796,459440445,581310766,804288598,364423277,737202607,605217313,294935623,745489312,59200403,15350332,884924948,575979306,121075710,162063245,958967237,331647513,528901107,538628492,680816392,837878242,993682599,447806253,211836499,200828540,180077680,220405618,41159824,26633055,893846338,455692642,363182237,301620564,654447488,639409008,46751465,857295712,704699634,370819288,536727524,573230458,528325504,662075766,400815982,70083836,405372014,379949040,233817196,451308068,702681940,957437300,280977498,264932594,240515969,484074513,621228667,185542005,737670379,775811308,458541107,355880958,248452668,250087640,344617468,121285825,953392961,339725342,395366913,564426939,571425083,959026942,327985369,327472939,713242746,319794294,292306832,608888903,659733302,731133807,791123841,732663858,172454737,782102921,749361271,55582305,799991910,990539800,357415986,264770601,839893217,192604261,413132870,719233935,643285448,482223444,630913138,19706232,961608049,423078280,232545508,835209340,466776750,892656407,135324196,126116337,622843927,896162152,150108782,995140831,289493747,337175227,726529184,987262365,622456670,341348304,802509765,584906867,319491980,871450578,816259209,768876082,514257358,36589764,732407450,94254880,412356438,816093665,}; typedef unsigned long ulong; int inverse(int a){ int b=MD; int u=1; int v=0; while(b){ int q=a/b,t; t=b, b=a-q*b, a=t; t=v, v=u-q*v, u=t; } if(u<0){ u+=MD; } return u; } ulong fac(ulong a){ ulong r=fac64[a>>6]; for(ulong i=a&~63;i++=0){ r-=f(n+u+2,n-2); } if(n+l-u-2>=0){ r+=f(n+u+2,n+l-u-2); } wt1(r%MD); _exit(0); }