#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long 
using namespace std;
const int maxn=500010,inf=1e9,mod=1e9+7;
int n,m,x,y,z,tot,T;
char s[maxn];
int fac[]={1,107146451,559805077,679209364,644158465,641102369,363599536,539157852,309854856,663484182,578095319,765808214,585806050,579773866,861745250,5832229,242744764,899032987,150478174,627860803,259081142,544918953,907400235,421968194,278955367,974067448,996965954,473966292,479920311,752161465,316220877,1575312,620898940,405577532,956413299,690120224,24521750,576078970,929871923,14422365,251368199,582439362,220087090,98361446,763414075,980250487,618104354,398723029,764421236,476998749,682498929,152611299,345470378,403024660,140864216,134623568,373126171,461157687,363224613,526497651,95936601,19447777,584319463,569582206,9045328,933097914,959173997,559096347,12442609,508362944,167332441,75538458,275742306,137855279,60332461,598816162,31223863,767213175,564190300,222078457,336060741,632048012,895642779,171183381,851161246,248744620,635103992,605016577,853414712,546047842,626497524,867430659,904851726,475501650,298693437,288843364,52298443,743602491,479708090,125625755,491101308,662967999,385457627,482257159,393222011,245341950,474567292,196002818,754437203,542706821,565768255,524308015,545648343,58680787,792180189,246899319,99934426,788944266,676012445,610686655,968999,595032530,244819707,511710008,902492598,586350670,979137619,980655027,474700377,30153596,638587686,420932107,353049206,281562548,921459833,881746146,850268753,711117420,919203761,831442297,19426633,910061172,862345480,293462255,542955556,850500036,181909169,496532173,582702682,168757859,76479948,477639087,930180103,941723214,28581913,268124147,685075984,53790970,672818243,581968000,842267748,947532066,451116854,333707614,650009312,886294336,868829344,613566917,695702195,853242582,485348706,229827108,827117592,492711911,296974594,463847391,649090736,204857297,760019200,942731826,544075857,185735387,550588097,632593345,706629399,898187927,854821744,297803207,596729075,466541843,798967520,743420839,198998756,526623452,952046139,82926604,924044367,23777891,924258126,450837733,723816384,535478979,53975412,517436639,63932312,156530778,807928028,305569485,545662462,29493652,721996174,49456224,480391065,526281212,151117811,299085602,522961673,374481484,489252071,589831644,323604647,153393495,268164416,48301315,90383486,172827403,800588969,757146415,169338716,192601723,398699886,675113999,139831846,135840345,475501867,530389102,499294891,415376,114785958,576550918,294587621,714006296,457685563,875018827,254653019,813805606,172340144,498342367,258170000,43217172,67347853,909565792,16783532,495844744,402811155,497478507,110424728,441813281,581794056,561458723,196447201,404666335,118379156,910698506,850677980,722054885,777969547,12568481,748065817,60153582,228338256,433273104,521949545,52378412,701779420,407719831,445935909,752708852,15212588,650765251,762479457,398970308,808076198,39427394,8600742,746536789,586283387,655840660,152366450,741393509,811667359,415355660,386594397,97783708,333236625,778773518,205743536,570866962,242211856,218690396,27368307,562235036,987935647,849148138,692637504,438371670,422227498,845152439,883281454,243833737,59469516,765962345,89372661,972779460,599040453,5974669,324069108,180699112,833342486,793755411,766196482,468608739,812248718,494936006,59143878,606322308,732001446,635032673,759041389,554416265,86609485,559966857,658825730,586359929,562500933,889750731,724008021,806898745,995252950,135711291,340941507,700915958,324648749,722436788,59758328,371263376,265906250,850300987,61732363,887464462,625544428,279914778,644000584,180090545,9409022,788878910,631046702,358050946,714475801,883906209,808412394,528517448,316094660,724209709,544375689,996952918,79329551,136597179,64972739,930161980,585237443,422015194,62785084,374220150,44615465,1669644,42241449,58647723,929666976,307936472,361786913,974936549,107912795,225369475,703087658,480748381,2295485,880634238,805196528,188324947,595143852,926866806,742851567,666743467,973671409,837229828,243910108,697054929,57085695,469594245,199888908,649491763,274161939,558233225,470545797,526807168,244714186,411969385,54080847,427233799,579691190,754963083,169559902,270720182,588618211,145404005,478716222,293401592,614571924,321950925,459188207,805552722,508829534,304228537,355209596,534491822,947251800,225966128,986142683,701643375,439729802,759944655,349343101,48980788,212468510,840398449,259450229,983563606,704289349,442694685,899297830,121102289,405640886,513670887,961729079,235861787,281870391,270409779,798401543,369530217,888050723,920492865,298494436,756462483,628273353,656116726,247544137,294651705,412762822,489872437,736550105,461990959,534030848,365932794,610954403,440902696,253238972,682492613,522303856,839296517,85990869,288079694,617973869,825208191,111668651,884343068,125800325,805525713,184783824,425093556,56305184,939279559,912326839,855064933,756764497,973478770,706513987,632521245,897480658,888874515,168891766,413551441,450119928,687166876,349851104,804805577,160016093,64401654,546799298,304104093,927880474,870230497,673373340,543880181,83687737,876297919,298117414,660162137,753032322,989583729,934814019,759023037,546967731,400707264,26634340,676405347,30684171,990757848,981776332,122464431,567277637,737511882,888156482,936882737,350634174,112249297,998807506,945210513,324630241,966957906,44930135,726576875,856312450,61329065,987095152,39417871,816679377,984659637,375956346,152201272,47401357,573877927,322199735,112861607,382991165,108819476,497956225,939019242,259568406,40151094,281863274,720198656,414608027,139227607,963111262,60168088,597743038,797673080,516804319,956903770,692636218,376501201,283454561,168830642,79852813,432775082,378591066,168948455,879838297,365353075,14235602,936696483,603752857,218851785,790227812,770511792,191651583,37130006,277138066,784685853,400295761,962694684,212661821,487912147,674932318,697066277,245419396,330984733,721056741,367606436,421835306,560478118,620682731,704015358,859346814,220108638,929629213,258032745,483594161,744178841,661224977,362005376,792431280,610644835,107880912,261799937,925041977,331286268,995422447,376285455,168203998,63915001,731950688,346917761,851595228,802214249,771727692,921586643,310280612,551069866,544064410,6811130,792676030,441236680,500440019,935080803,199237620,124878394,238096591,732880514,583967898,393771071,423889038,567003562,740304600,211768084,89921218,147206837,187655305,873138566,751231582,107228569,787539126,653478705,710576505,972424306,275525858,711211981,682495521,379750380,623534362,834892236,332606953,89816323,714130414,335160196,17823426,465697749,447817657,728285308,243276029,532995050,545163218,716734025,688099880,554749550,787117889,502618954,543915886,907685793,60050552,998579767,731397402,350274220,838528120,797848181,198635873,187586151,515174333,126672033,395891998,455781723,586419431,647132471,935521357,172428290,780740034,447063192,265212968,406468142,159554990,833317992,520653845,802837814,332814802,887420150,14211262,605911169,423078378,577063899,970055531,513206217,40607687,351001772,829605980,250388809,148577573,449800991,727934933,735023078,487998999,737738750,634045080,744227785,585552623,856259313,386799500,296457528,441140793,343416042,82104855,840750201,528005624,761748690,959757496,232253360,190349508,363157570,175671239,862776555,513365505,713750699,803726808,128024882,881788966,244109365,136906899,372302392,155570288,249305450,1559745,397066469,25720042,626251836,177573201,695345956,677752342,793806704,581977030,646625129,261384175,253117073,245535187,757717391,80513018,849009131,439520189,712872275,92973848,64851034,323214113,664011932,298352021,255712655,946042845,747664143,711816007,691151364,285806889,395396851,444090941,95039844,522655892,377908620,257703472,659224434,26301094,83002883,862614058,475057494,80729842,339308141,907519187,223545290,614010914,570033864,279454856,793767325,430035302,143966252,664989237,213302213,512045319,735382383,661411739,827348878,814721633,531511759,271003610,642932826,195888993,54530329,8792644,141282580,142207463,576798521,540842540,369088993,10438986,881336900,457882808,448656552,620851842,352488342,286398811,731551699,397201286,352032421,424438049,690333383,212938473,170367135,348384180,900118182,545454871,509096183,557219900,269119299,71735354,971188122,827544702,143313131,674471405,617909056,356557690,678320208,72413193,727559899,538479815,137232509,677711203,245038045,533035983,252381793,579001093,289752035,908061115,81830860,927327790,717194510,66404266,587040263,864886893,930123178,168706834,555972231,346540153,726092354,865071734,691794731,195290384,505039565,105369595,318094322,251055417,97136305,259423383,615768075,48226379,49055565,349551356,439547835,441914739,783331349,14415592,785113347,698578769,256348629,627785281,437879870,83489485,444939632,669721484,951712820,16691404,66247239,109670626,964858552,811793940,43692008,52167191,817865822,989876896,873199303,943421142,307390891,26423599,908425681,568639586,763827725,547665832,705468334,515674128,103148840,867962375,143066173,65688464,288586996,993416534,27059824,350016754,249679480,483800403,620632962,182282878,917404120,735051019,613755669,699187663,778614746,296269301,172717571,946428264,64227251,302130199,996122673,29653283,566743853,675135087,125757468,23015220,69144282,91963875,747064884,707518700,602139210,865946552,304609790,315792222,79909943,748566338,444243246,677793008,71369280,316009903,187348575,698438828,588943683,653637010,262263266,109838563,579202306,976768405,653611079,743379209,574053420,621976669,644544622,669880848,656217362,105574531,29530499,61251444,703406898,452293734,304173654,962272195,443273892,902817853,965863401,542432219,57871728,483381085,862802054,146817944,34538816,601045763,654297097,974686011,488641593,325636655,196493142,837122513,261912790,498769510,437843114,616745496,177043432,781045243,215203239,630621321,267772361,828224642,815108093,243906544,26853683,950098683,950937270,24585059,910131508,933245637,398417914,613395893,668061275,31373935,616368450,776087191,791289062,194702413,284301461,238971581,914259332,376484863,937988951,643201093,511371690,217011832,248828832,214825867,813678395,557301633,85036725,73710858,408261121,231162188,911398531,312744814,631096421,372821319,894005672,848952161,365531126,407261940,835498847,61879608,958992544,821785476,580068092,825545235,489515035,925152039,139924045,837893999,981726228,974145698,914456118,62506502,599381336,671342714,253502443,724691727,493000568,796455047,379569031,454499514,636817583,671808625,133580252,332617055,48407083,238087006,288453502,584070283,525709741,463044231,946237212,266574253,665038715,345406040,342052927,910291942,639275237,666894368,197517090,800533801,114985663,683569260,727416461,447668677,845963889,492237273,48958052,14863281,982399964,84066292,450387329,521347279,581318867,504201844,817001543,834860913,452479777,797624286,393997958,662570964,763017204,710524918,573783638,722384751,93189280,368925948,774578782,128141880,57577699,672475624,475812562,780444992,956113007,31158979,338903704,740594930,30327041,196133374,639667205,784067427,45060610,205489214,609897705,890030947,707609521,806047532,51697523,751385829,784074598,879021109,464456846,224012738,206786423,16481395,757595751,172115341,115439068,395201336,543890274,677667796,75307702,472939116,282517784,220670562,746611934,116261993,691436204,991857982,73185230,836720967,562519302,557278802,856268751,803489706,379589733,268838846,704823268,422027886,447984334,638736741,173784895,936274462,513000960,600569863,903630901,243624360,10215879,299332708,745649909,835492163,61570384,250649611,471338418,656946705,762291053,481661251,964221559,163315222,376190954,77886816,938269070,170095245,961258156,463372147,647118969,95182730,521051639,928132071,357479404,440006366,91068149,596682713,502285607,27842076,814435597,115435332,659725221,566804955,555863276,954436899,495022305,621840415,419016530,187930450,950614205,136026497,650427674,588220375,99515953,19179738,506496856,355847369,474430173,141544165,29368029,710729672,194678932,233454730,232785168,981331732,113570024,269240725,771211236,968217984,482504225,366384665,18878032,859670660,908756610,904676787,564758715,757490458,789798345,196234471,877873054,270239666,83412859,39852073,759243154,994645885,277118392,91658702,565097382,791195765,337945304,79874094,26070851,613650278,370886950,678481982,702807165,595881374,969808707,593441490,845233368,112390913,287199918,199287301,73194471,12722112,730341625,143352852,898432986,960245410,96688732,103056890,357128875,220909560,926269464,275050620,677948390,667314832,671563881,59546001,781014065,339464594,886951140,956300519,267189882,483334477,167240465,469826147,242791773,982787195,897053425,108312174,404419260,213495567,329493881,194495711,839079953,744394023,799886608,324061977,4828968,479334442,64540172,237622412,57802491,75307485,271788964,367246992,449337229,750924279,27562780,135498044,172547388,796874733,559021338,381261137,277717575,6508639,182579383,649588249,369091773,591048681,547541822,203770813,237482332,884448724,811637561,913670594,171861798,660521215,594481480,353339603,705462701,578624825,200578945,53887029,889410460,65382100,119754265,444667960,858172947,839849206,727527500,363876491,453708370,448553303,192345193,874653794,516251793,655083733,579917597,736265527,943565520,114354987,322697676,84996211,316439118,321767973,622243748,33541892,336307844,217544623,765527479,488571552,901558026,224426443,788132977,891740370,79799739,285783983,495353045,618898635,566290786,876944194,893419849,337227397,183011467,200502210,119584347,75044998,654322415,380858207,41105587,779716363,537171634,416296106,996097969,117632702,744653725,665991924,776830268,898554793,98150112,649498583,617376992,914289783,335353644,535714239,57011781,176088357,130970069,54062950,581932933,197823988,104193664,920088375,611251733,281925319,603541468,520167099,54329101,419363534,999882733,609974294,144428843,787976961,965429853,188902380,663077658,21156992,264583298,160398980,117346006,365477695,907509168,141023870,151319402,432853212,972573872,422341486,932154665,990918946,469793622,548515509,584499542,384832279,607730875,686042136,568889025,252498130,728066225,450718279,139074490,414985236,309143522,28035029,173539388,341441066,210189977,651481497,526650954,648991369,298136906,324582904,271280653,28215403,970937898,73200626,438582079,732533504,26734774,500780548,898813354,834047892,393478502,439473227,780122909,623210256,719920686,558066773,653072279,39052406,322961340,98850072,690363849,760185403,276894233,820701420,754656474,521509517,940004978,460373282,579784574,709826006,591327786,213095340,651081062,631039161,799429582,205619551,333519690,461415770,199901656,45606936,665103395,648597040,358700839,367292711,650317594,951097561,305315917,643638805,42107699,624444413,490712755,576235495,560006119,745174361,896387115,789998567,706156005,668123525,258950395,585694480,810258572,132735686,686692315,189425696,256948933,412101608,131741634,673464765,987323284,209922927,981063997,739667609,957633609,959034974,387371507,337587116,442266621,199866123,329784980,357758924,50074863,837041881,563432246,240113750,732795600,753526942,479299281,841799766,332678303,670276685,947815394,2842216,385330357,966879926,581434438,886495348,397040122,504962686,123693376,698358362,91552734,99282640,954061253,296490792,696199419,162053428,511951052,128487469,663044112,325243771,452579108,328827203,685707545,30429569,19400253,264145497,59586779,299172297,835433918,464938358,127134110,33971220,717975101,802237942,394125648,401098691,27389706,577786541,35368452,303960799,20954810,587564278,318951960,349654693,221376767,443006185,985325842,773206631,834645521,856250990,554999881,146299241,306832604,405462479,940588421,942749789,512117445,204355779,680164492,76508631,896673698,126132194,573592106,251680833,586600424,763512297,851729659,30977140,117294271,872687840,705027494,155345351,450398100,658259464,511653547,122784513,563821816,363172638,614886666,349541490,249358677,136993731,258379324,54999362,20843784,278558807,628533988,472935553,877990835,873758230,240566962,845984324,93940075,717953996,131626578,765533635,627506214,587220627,460004468,187037910,443040223,42987704,776264326,512808433,698604673,930975319,652206838,793270300,599178777,113754130,344159107,911620065,291733496,185579598,867809325,297187956,599561924,522049725,566288467,481989863,930168992,53992733,579995261,744715706,193329709,125738917,322096840,335416359,468232116,550810519,930373681,80674155,142946099,347339841,3679394,262877922,216214183,472012302,760519986,609913278,570074267,408626290,559947225,603988527,694873679,271596392,702278033,332139472,847209705,139873662,307320859,508029503,499377092,499571407,213218151,444800132,584953303,464599136,287080720,381815654,328840505,613227212,164752359,62870178,338612335,847305694,231214901,309058615,923056570,741114654,679474509,943963703,86117128,173607295,192205742,854546438,465304689,580204973,693571936,221722420,743803583,910097241,563781682,113007508,366759417,729430386,734084885,954840109,87536532,821577890,612067620,616023889,624577416,183378516,712232206,937341831,929688418,895609896,948536557,932074667,491512730,333962357,888287558,909434502,622456324,313577942,396397359,836813268,73963271,203528675,284627321,978490631,926036911,928078729,966538801,718446896,676092053,386027524,769016475,417881441,419449519,6622174,184419613,428377643,862478095,616873080,68030466,724205533,771316604,111897624,100980417,487626661,403351886,197681757,403508109,851600426,132801672,715247054,701593595,651667233,770437268,24911986,716986954,780721596,635845774,587942632,428368450,830567832,371306896,637985919,36335795,703224736,383388563,990426067,701055524,398619836,291291997,68409439,772410939,967445876,510553855,661249755,6734065,437410655,176021640,130382065,684750143,189239124,293020859,437611321,526519406,471149790,68322490,764804584,212032037,199007164,671683885,943653305,279901097,724153585,600497805,559782639,405755338,470411531,230505529,567659902,486245922,811056092,369665871,228127265,234484080,411331165,179518046,608693296,734959327,48314078,490903812,825132993,918581297,479627509,846464473,761918447,343807435,436552374,224163026,497516166,479946500,985084650,17287926,447018815,299183050,145906122,868553027,193468566,881713809,786976399,309455313,148528617,246026996,191267209,430464002,100931272,160684257,596093059,338146211,265187723,448465137,882148737,629532985,248528148,654572396,897437810,591915968,319640243,696312467,611578390,372312361,701445829,962818755,860362535,718311808,76142147,529726489,24241426,414119827,320111308,336720842,302177126,126491704,613897160,924335797,816787370,974886682,191656767,682815119,567920383,793851258,241107368,761444952,194742388,621889419,454022261,798830099,690972016,903969041,210305537,522929419,940567523,11723489,838405179,150961869,157588295,11633075,230720777,968795345,540124639,447156284,325334066,204842030,830679914,741295810,743716196,346091869,538017325,459776558,315284618,55047278,115312728,4692025,318753931,991445447,508133625,473718967,216198217,433344718,294829425,131899998,218129285,677013556,932843935,639354624,341598119,878471898,169501510,855998453,587573660,499944270,180002392,490957526,302311490,791145434,189039628,699739374,311881126,121266080,146729215,92544232,917084264,391859035,4794797,798890367,453362362,856859395,545480202,971496521,814906938,379109076,435327356,193135182,922714159,265682709,552348113,808651347,468099850,257109020,480752775,193708013,421623838,139413479,820519069,795354000,273532342,105419548,184110060,246087982,593253319,79521617,59883031,528910967,598142207,423151147,32072083,322487421,288750955,199843514,5095624,809668786,79716267,472022598,192830460,995747483,756147480,715317963,366214156,540894424,310763081,436700379,429277690,667079481,311514806,748464103,315334936,398078032,573147130,187438671,99630959,103129190,316486674,912169002,714885313,244169574,997082517,384843585,120666598,868729680,132813978,807137265,940338439,941886088,353502954,454920772,193798014,937409008,137818624,755771078,481544618,459710496,940524812,958128854,498645632,515132481,324273785,947549662,542143734,518804963,153647676,593471448,833550543,250090645,89990507,579250879,2388484,593524514,752057652,291568668,811327365,365422560,996164327,37557960,321244755,262105390,926249712,987314628,168966149,3657915,492562803,137774364,697611981,709427437,708146737,319186712,448070840,636177449,563983446,776902713,50890241,801871097,274192146,436916208,413045253,567482968,743405594,418537348,102670030,210729521,451751420,208016240,925347821,921491439,986220607,647024460,677344487,952831975,821240174,499236336,623193347,70121843,893732627,252978558,473981189,718775566,215948550,1277567,749948197,253263870,599092339,348350896,358655417,92457810,583160135,822890688,340690733,141866945,528735091,153014838,293503505,792770688,581830879,902909023,509586056,47211054,689449821,987597705,864507704,95792164,994038437,644755481,347046911,734275360,752213561,108087469,106265119,775305697,810184598,512236469,843924853,586524553,125354499,155500407,365421825,457419472,231048116,951540811,193960834,586696485,6035002,843801012,247662371,807684222,947743059,607924966,363840458,343043237,31628362,674647619,957418529,208983731,568392357,592453528,983211324,191642900,83735188,997474832,893327224,648755177,763538123,722834776,209244402,455804196,716850596,629666477,97587647,380480118,793797606,31462446,434078209,722262801,149586983,891829033,303751319,405670141,400254261,392838702,516564199,797177914,783203950,795179413,309134554,855159619,296824558,839617203,811476109,990779998,488334472,47902070,880648014,85060063,263053337,117412078,985650598,946752311,419136857,325362513,588444116,116725054,942971003,984807268,780072518,945288110,469073466,792003268,906534263,551028176,238082550,689363231,988770034,288035303,990826116,115203345,199204020,5871750,443563763,989944961,717903632,211188289,797385788,754047147,155569943,525310983,146598405,879917958,867292155,596737944,111145334,116814362,130359475,65516896,711553356,257272757,800639067,748822937,876432387,268844715,285754648,914012338,337234235,878473104,451373308,773873624,327120461,473672652,439847431,379404150,358541327,432529045,113595532,85317496,462639908,252730810,632738698,920756860,54745397,961812918,26499318,685511993,296301818,459642445,654611901,545213692,318351795,951490591,845395490,382776490,877658697,273404439,487989369,256635012,41815820,427826292,370999052,308084349,715657404,843321396,424629988,138829244,971901418,439397708,675258797,190324601,949238642,867463339,89183561,845583555,285201003,54718463,68493027,918908541,934281721,65952114,115836197,438675673,329796660,741114145,170688640,613839978,246971298,368915438,275105629,927129495,44673585,522626370,151904385,666247477,11034295,553115973,736481265,430792893,325912072,163644615,312363713,28447959,708382039,526131620,337778689,643205214,267512809,566782883,252551589,514003160,956613828,330419454,497985400,432030917,409094906,932710247,320060926,55291696,554917439,919398906,250993499,687801469,749521773,818036959,853329772,517363885,754948228,124331004,754363835,289925139,324458366,647362373,199336973,795190182,759415866,30954813,375598506,414771343,909210595,119812483,700755004,13265271,907013091,278704903,878065545,350477813,394359162,40070120,719566487,194044866,19360802,644419646,538410830,628514947,782386712,805940809,568881907,72505010,424989675,523809523,560500372,628422087,830324646,321685608,501026094,871108711,268675400,141938430,50590510,96029674,930059515,760581888,932297089,832069712,747776616,317413783,229386209,937289943,198768464,107918293,241822340,154527893,515625587,702004730,789870803,968162638,861828251,410971868,99199382,218733931,811051461,108157516,739303690,707469729,338230961,281950342,474683954,478806302,747407118,548042577,363810556,951545265,938222670,302020341,393708383,500083903,396133072,916317352,497196934,870850657,806683867,232222235,927957338,5003231,294813632,836484636,795382466,789372556,726997875,766119778,569565538,396201245,59049178,382617671,477072797,369721783,342634621,911128874,296229203,86301351,609696820,14572600,621340527,183888367,469448617,630735799,477527263,685432978,703397904,407218934,48845205,71614944,140231825,552133875,961921035,958236143,612842106,903284998,732868367,508543739,376263315,828871132,415616232,350095207,942401605,155864979,800362473,360070086,26031303,393412897,48755035,347115769,632078189,863250534,150230048,763864011,802627671,559518219,216665960,834544566,908760486,355456809,701253820,561745549,106460787,744954999,341934027,85883684,352946234,569536822,814053802,496278313,765506212,784139777,982076387,56103640,965931947,279881729,733333339,934237219,432445966,747541026,847302953,503105966,270177936,28109541,563443841,312319329,459878625,512506831,208372493,214314837,748932782,803187381,183753738,632548969,62568726,452864462,16634739,626492653,818220387,123301859,361648749,180898306,268151658,493448019,298852345,278798734,68718097,459948721,294891752,765504766,315170969,985594252,53792521,770351508,827351663,279524210,404206040,484050433,793946555,793118341,404917720,749724532,321673283,822303356,184607674,92441916,97830135,358933626,545104222,93052080,378307888,611751357,206861090,911268409,989655902,457564227,31131935,947436015,602293534,304598573,389038888,662741752,699689146,573188485,316227381,903947795,864326453,704204620,96158832,546842147,958542649,864869025,170961663,774999229,530328239,349055793,167831173,659394668,753712331,582032345,817219959,559214642,229070827,934331767,628303842,865023876,718498895,528184248,559961787,746668480,707233111,91352335,657496548,251818074,288199605,555189268,608823837,964833819,249236264,297020805,262774210,473379392,229265100,634556946,243591881,453510559,385388084,542366534,9582985,862206727,20303770,152267158,562008185,830691740,636134163,226087354,681756977,115792198,565417478,132026969,657564216,46819124,53730313,105764429,578460779,671247758,313132653,83676143,781307067,310247089,379008804,56547945,282185454,977489767,263223296,94974805,442795120,21788247,632289515,888860570,457210799,796616594,976656728,650167037,636009706,462320111,256141983,876216454,268795108,219963869,452130570,152028387,620695667,469042034,186801565,526335076,636578562,479037032,366772204,732408654,859354557,385377759,191659036,179536173,18081311,336074035,553033642,875352353,863225538,101577474,555731982,491415383,553084997,53408588,829373573,410724146,919273670,143357390,9051229,486728022,809437256,996049638,903263782,586611710,34185477,823981167,326686486,917134440,94825580,312828689,231310558,160150665,379278321,469906415,482926441,893068324,141827977,882700651,365864597,519560661,111873860,540818053,123637707,859622353,176377554,229743519,693305776,781825138,540005807,766981391,292411226,593938674,898227295,253992928,950055170,981759737,186576440,766465400,50118951,694821975,259165544,688809790,650817063,897965492,96594580,520491355,565456578,748710556,296527297,410239606,220797542,749296077,813409093,422638517,26724420,152783894,519397500,46038513,181681081,652904189,701572379,551096742,663329044,176317974,362041517,288669565,696628828,790276532,795808108,546877617,796426218,775025061,587068363,699871484,148505764,200607928,370732451,146822913,278185962,972809991,573509777,164246193,277209248,965149774,514994610,754091823,915265013,760823221,501404039,130530532,681242817,457469634,745638450,793706054,105200925,523362944,923043932,862254647,407356104,105380350,763025936,912368644,2989898,522910736,394923655,42117338,777901604,849570319,488630304,566449613,243034420,464118005,89120113,424450934,800607974,871326267,637939935,545097159,395358411,726030473,907816292,956856710,982937783,994287728,719072900,744016775,490676632,990350617,471929788,753260140,621887590,453019482,292909707,891034371,238296988,542620395,462528877,184312310,369525491,313528213,38124644,502297454,808722011,738422572,428387930,330318264,798895521,631613615,75853166,862028984,508267768,100498586,641108112,530247647,761776308,443954530,699767918,537835749,525486772,134571498,696896168,849974789,449939558,805638970,149268478,916915977,811575797,22241923,512277222,23466885,112891394,438952959,665736716,698047673,168631060,250474300,606870929,43931879,463528680,355095535,154281667,907720182,785149129,486362776,151054828,85020958,179111720,534189446,237769647,299744674,593926876,48053248,482335897,892619781,993649414,439741182,508038818,270183465,771818046,930425199,83264202,811944661,723407599,16542261,812668005,419096046,752550134,154860541,883929124,986844192,988557002,401382061,67620895,115042726,121061403,939190858,848924691,826073768,319954157,581071621,871705611,764368449,427351467,242254724,152373822,411505939,34629406,631379183,491671763,953240917,254524151,529840945,570308920,428877877,544811678,720519967,435904287,697606803,849489362,541576570,589672369,26011548,847509284,280555847,548430222,935250524,208184231,430115071,181134117,354176562,874464388,446477394,200377679,767434657,767288966,288749667,206330671,191275474,596844380,646861175,752825233,366033520,753134199,329972696,539562642,156178713,131772368,772199894,544099511,155855128,194916555,185646898,256255312,473139604,146162018,979226446,648711554,340238509,584495484,454007135,197533041,472759660,687257851,927330853,360777215,912609549,523696723,401421644,792476159,446012138,246329273,271198437,8300915,538044438,295294842,713419072,25058942,598597720,865177945,848310765,486033494,859369491,304038136,5377959,845991325,810252842,817928963,866042171,152438502,670564895,461763427,330711333,235481106,77363677,837898265,173414914,724464507,402525386,835830978,397980952,551315810,437605233,697617046,620721450,921015986,866066508,701453022,784352983,721919690,987404851,490065418,626663115,154495299,303822193,72509488,784853613,281230685,172493030,510446188,951188269,181224475,510650790,521329716,79363961,607307402,742957071,596949867,130653048,498928970,448224525,145135624,295726547,930570143,99791277,467192613,954448365,303076380,191370134,366069684,524956976,677309335,465070856,771759239,644286393,936868840,608014758,272814771,698130352,17704676,136535933,670999343,538771609,993602760,734992736,193370243,32006662,48824684,265858359,757819171,149716490,880826935,951279549,955098935,701664398,450039887,967888856,939889684,420720352,443114259,109235125,886867149,564188856,759427018,22399833,955654747,816730090,48527183,944169450,445129483,427071593,188875807,201307702,715555451,577760366,365537558,553903473,484458461,562364570,580929149,697013456,232629505,861754542,529700323,959507688,673032615,355168380,326159309,599517082,313027690,626605289,425343432,181594759,455315503,360804087,60511994,356790137,668422905,742513075,750208636,410204618,210143574,286273596,810028347,612515537,477169522,67530822,965656187,17723383,369499175,994745941,801756649,44135644,590906591,550034231,226784434,413157808,359960756,485740665,729604909,347687933,251867424,936229527,65822009,132771262,222489048,60427024,407934361,134437749,120587974,450883789,460076831,267193060,595916891,530947917,50253054,160781137,456152084,65065312,694188722,676379162,207214810,459116722,895560303,329795333,891996014,368422050,124804049,692229472,751677875,387549818,107094470,262322489,168655116,127414221,127290321,696929170,920251227,870911553,10679073,523551656,323940868,816929577,817279053,947070975,424610493,555285442,483924582,885053740,984402270,275356603,807755216,151834896,248636352,834783869,342008720,397154977,167087470,96154360,873784528,992692236,157167077,490222511,574400690,931065936,989612191,879229923,903466878,473549421,558765053,781375314,279153607,361583925,849646812,530908116,11779782,181929013,368114731,384117784,614562174,31016465,192200875,339383292,432824950,278928724,588320903,606224169,388728584,767789944,605240,381205283,22602811,218107212,337060250,770468270,36228319,508228531,249153339,654931776,960535678,203521321,87626727,909458706,493952635,894601453,307920342,463556792,322908524,63753880,242283503,585065543,877718665,202649964,466501375,112078552,658442906,697450276,92255682,419292187,169999754,59952286,930731151,573074791,454538013,476751412,931433486,169931105,15570863,656835361,930762614,352110687,564730215,94331513,243133049,655471890,782066883,242612658,744158074,384595922,796850043,760217410,526627922,196345098,306534040,945578836,920947137,974375849,334326205,445900278,849929912,385444375,239473327,9416035,483405622,191214699,334547062,997233464,98349682,570901172,262989398,327192258,184790555,882121662,958445403,858663278,783054273,490312790,769795511,447164962,820483088,529172551,909017757,231988936,932616287,907485902,768208088,361441946,888146074,387636812,362567344,35494306,732526251,137603545,548032144,196039409,931021597,987451457,582627184,52369532,971149798,958090664,880462874,407518072,912118240,964153946,644572432,426586939,919419361,157418739,371739314,615861761,370692399,909433461,222125557,541985758,944154377,547463294,986708498,536995755,835585917,410822698,30384659,310317874,940526817,80932302,648517190,663213991,373745190,2978881,629489405,66951748,113312623,263645931,834203858,967945295,116940940,416532285,256853930,29483105,423574692,844148073,162638132,876379959,526240263,918251537,121163959,411749850,702823274,598995963,250642319,80761335,494063841,147050765,489134659,454479158,129015470,889479102,308186532,980899070,351359004,516851727,690998709,175504139,37542184,5571621,75147725,197559076,180350107,478177973,612015056,527651943,552162842,797736554,593443248,839987038,823246366,395773110,606241871,45671355,897002443,90725391,94230023,384547635,21430807,581357661,618924870,494118647,273712630,801781337,25534662,85981391,366267355,586444655,442310407,651528902,661225829,815109260,682189174,869601706,787940705,633021147,64685867,666493603,337651405,126747959,988034294,167057106,946867127,310079669,655392623,808701401,921736853,819114541,638544222,471631442,100107979,424618143,502371023,122511053,905845514,584314137,790485759,261970285,413972507,944112951,257426299,785429551,825871994,51773862,848886378,396267526,756445317,126925175,972951283,716569526,60331080,738079754,701506133,219886595,96436642,271834916,177546793,314738056,494271604,435886744,885681419,341126370,341779962,746328981,799261956,800822574,848518926,561011609,24345594,558751647,488335568,228329908,815463367,866378998,869492348,887264865,649106694,46765164,607061640,178904848,124722795,425675181,49187570,603834304,446331630,932575078,454804469,188054995,928529467,470209383,494966152,231504971,957939114,122078198,337515306,558492354,351235669,64814326,880615277,72298073,828744337,163025077,933376898,149038120,989183409,52844822,985593892,329837066,725055952,4528059,837168087,884406233,338121343,133248309,147503783,628460938,364396002,765215899,886677604,529664065,719537828,63239925,869630152,357875411,426305490,637983821,458037451,978119194,412687469,498194123,685092513,210721601,632627667,3961459,317246521,959262804,807947426,975266085,20121898,89185325,825283988,468444339,435887178,686721323,500860184,228374231,510020354,282092463,982966892,829543369,146168758,12050683,129621197,481987595,405196353,607291665,973851619,758245605,164164627,370795847,76050898,735643780,827722926,154108068,868946348,208205431,800461354,201339230,761123504,289985936,299417930,912554918,918513230,384531928,527015648,517549615,868169900,322096036,988894879,132276805,884369503,111743408,547838438,247310262,914861719,609673656,174368041,985546115,217650875,782340764,724929305,966322010,852304035,449473513,783630094,587360154,750642922,593090119,262218995,744911735,581282403,105182284,689189630,481737612,664079643,672675152,363994545,555842733,626539241,271517055,810853769,973391629,567033437,94400535,130223610,310769264,380766745,469928208,145628232,534748128,660389112,382964872,212842957,752708555,59476749,296509592,616831860,117842065,378430921,309829395,350285832,88374104,404149413,309066078,558661806,492836583,423750826,155133422,202330828,145364504,620676040,342138996,663307737,820398475,808454200,981899817,546696895,208761293,963774716,968375295,965328448,936102439,206282795,295627629,996017320,3811515,330624860,717946122,16741224,398260081,580069277,908353133,488906585,110521739,30569161,234964291,80281513,414236650,336908710,454358793,450727414,513021593,280700600,609679705,96079152,108916243,107971406,962670136,34566831,725889057,411765386,149130988,534279149,609799053,830184839,469970550,56838370,214569244,826025098,102488577,401776532,483937604,375297772,489310502,517845614,973417700,148428940,811053196,649876656,319261078,979071936,468642345,922377372,713607339,474115783,946802154,310792516,289594327,156910777,722424997,749805383,277985222,219932130,487075978,136961239,895001126,205625235,211487466,200048852,11849047,73943059,630135090,701050258,978125206,684265803,536375628,552965451,398782410,206241913,889674027,692292858,56967115,863002719,771926344,812982323,437913038,790641838,27236531,201252328,378698060,352817240,302631882,217598709,868168063,480698499,474773010,876412019,375472836,442413206,937210795,832120781,915529697,810551911,536944220,767557384,418758727,361003283,178598958,709545031,578519730,448564967,89010120,247844667,731467618,432551669,809944745,854684600,676526196,232511639,962090950,390009248,975808258,812283640,403888976,595405397,34221133,770779245,863066876,594845000,134120574,374647549,531245275,857241854,857265904,567393268,849122672,789013621,113917835,828454750,642648400,62553593,432213197,624148346,654844001,621725636,83203491,621143544,726089763,741504235,262034566,98533460,597019590,564827277,36869004,652975242,571007758,977482822,826300950,934007482,211854468,905426828,46276857,478982047,684574590,229040223,293838397,409534564,439411911,834121669,634939692,133770918,620956265,454039189,688948972,63767449,175327679,110933513,633292726,117263578,979744007,544744689,528557247,48562889,989729668,472970036,581888270,276850119,802100365,492337064,401805356,856718199,88810754,671734977,108496295,75057840,275791943,664888764,945204804,809192204,861484281,419328516,787873321,508831870,416208822,410260274,988955152,361191448,398781902,677880815,142990728,314836111,699605137,897162044,536271973,636998925,221811480,886004348,644050694,653085093,393470607,120855817,768884051,892168027,262288506,488676042,836225870,831017977,828883117,981671640,586828879,927715727,715108783,277714559,988063869,694383920,807762455,287466494,713448377,902649100,535116329,921742704,429126605,624500515,428113849,494570163,270145350,556926990,590098114,363293787,642171590,216856467,175657516,808691930,358283154,67853838,479719850,825214384,514359662,996283144,430538405,205394803,19332138,895205045,710192688,523665938,932133547,517718457,715264908,818574611,492549025,427084870,187800811,628829100,188215106,143380801,709026752,759002288,484492064,364455291,966707479,837453770,482764258,919717789,297041414,727771800,375730434,140909847,513196123,15369004,742784839,966548302,999738618,748510389,748342116,699766608,30305086,130016019,403652653,594901690,645584198,661412735,859898679,574455974,426349074,452410737,654581682,28726649,77123823,368429004,601475460,431184348,832473701,172096141,80383086,316340630,666861325,33107859,819801784,865506733,615250929,876108626,182045350,581418893,96311593,523597876,17622588,797757269,15655126,793616977,668246370,160630660,964118631,15391652,56150668,815626120,221842546,393720508,875641535,412237041,478199454,241071717,767714339,203191898,978601387,552822041,138549377,417942539,264582598,81856390,234947456,277650223,581708983,880691101,467598076,625278603,299893553,197666986,907800444,501938887,725559962,569600455,859921080,986598821,893600713,607363865,861338050,870740081,340030191,481923877,945358400,214956689,71038724,264688936,398444349,449958460,771097082,41076631,369832433,770162507,905924748,183658929,896884790,785804644,912354528,954270606,598778643,604867835,842065079,495838143,286875008,219425152,799254294,423951674,624114280,119813352,714874414,268343768,663560047,923820379,366223170,341205900,975896867,696623384,184827796,830126743,823399038,286246546,496709826,934953895,572785751,183229029,921075273,161960209,538244672,910171678,151945652,326083992,331910086,908732533,188622572,13527023,484862577,541120825,432047901,941211285,287777481,31728844,951524114,832712633,56287048,142493387,652822305,841656666,610289231,282938781,503140662,540979506,162683802,169823238,881334012,961773117,72128915,629786193,979670619,230477028,402106077,794471639,190395535,50055621,91198469,221210182,481161431,269571439,609396366,587183657,279364087,513958026,832671304,565647910,320001298,831650763,371926819,76770272,671672880,199774070,377865541,302464254,341080135,644042531,160849952,365500410,921838917,421943723,170960052,549348080,52995235,655814211,494210290,397780223,104494341,825689399,87076222,751040886,717668287,55212870,119004660,580413046,317076664,633010409,884945562,895966774,114495223,672850561,431200610,671006344,679872740,713879575,72482816,283738625,888938507,218139373,954440108,493689107,974044014,321889979,158471181,214217407,135625240,919788603,497813276,79499595,97784562,100228913,597790155,810904041,480381639,162490176,684748812,957200574,909426167,683285538,585281399,639655136,84632985,181994733,826696971,960676473,906233141,21121378,901451856,823154790,2902192,929893103,670105278,642380089,264686798,941348051,277813439,445446563,752635906,902980332,105074578,814362881,467920076,427675611,8521003,314431839,562608724,345167956,515767294,617304201,321587328,406024012,132278719,726229501,600233962,472901360,885537778,249429164,785456666,674533527,888167735,10065330,309461521,196741756,210767592,753152516,60625018,849578441,841629667,468928447,640885103,983737173,73330961,915099068,624377709,849525756,60517502,114886454,163038122,430048364,141596507,551060742,583216446,143407998,918542696,179435628,804930491,539765360,315266469,494268880,391413644,823845496,161083658,428887477,973849550,240477416,727416538,313294171,881769105,193434473,147301263,946421040,917891624,63641538,770955505,394899231,678171399,434031342,451079175,443618781,634121148,842203531,1807425,95905616,272168573,353782904,175638827,996380924,141522222,653867289,46910641,894247956,905754479,823173026,113252848,267728794,538609927,862941821,992194188,975226699,831449564,885362182,49790705,411820693,663971804,983946932,946464959,864162465,70298830,978954289,680922328,116667533,665516103,791371507,44771880,484444661,749816133,894838313,933305518,616418505,704840030,241427979,659692538,961319002,995710133,273943424,871117927,704279434,510693796,329834703,690369886,281804989,799146252,220356705,341717691,55398199,163928347,450861796,667020392,118238106,341968649,563796647,999853565,630585326,996135761,75201573,640266394,294139525,193170365,626642230,638428173,774625892,53533202,768834255,295470685,146628973,59342705,182299808,503912861,116225473,176366171,256473217,612860517,702144552,351908785,795985707,674115061,641863188,966269658,969473023,68213963,918860977,198797634,2947098,566144751,745744394,322633051,505255660,106954728,325145582,950334087,753513874,419792036,406578925,757329093,471703615,393556719,144571505,375444447,21686669,874254764,304644842,141952086,837580332,530861561,219698501,767372800,377516953,397091747,75061610,749180338,161362528,288897720,294206968,60065457,976521022,754787150,270285846,380974020,451709693,426176420,627655552,32047028,355876825,452433811,923770521,677395736,441274033,311867912,800849785,661537637,799289297,556003302,657258899,927572137,352886272,846650652,338657310,988455813,535099780,607636771,816701166,44086947,407896543,490329417,128635371,687265514,579659907,759048941,578690901,291397055,787113234,252851400,164950881,677856415,744064735,358757251,450562136,617715754,976366438,249770937,701220427,609488927,144453590,795949633,242444386,607715125,576861374,773174605,655829165,750941512,245795606,575125687,43209047,691263483,760649561,600624983,215263617,911651761,347049376,16011198,10475577,434596327,646820311,43235933,360639233,728620948,672056268,170826012,88327015,193266837,759404319,811707189,275928212,724907442,43792231,36292292,77927268,912907331,978578801,82897702,491466901,743334671,987488759,762625463,815053082,22556579,908499163,723630413,943554485,933704825,114495791,680244574,704711488,111439262,865233543,647630109,52347419,968677027,999091970,556738299,586445753,39937116,768945489,917909484,467351091,482254337,410651368,7987297,368295944,481742019,718623833,576140617,301479375,755652757,218494741,763514207,35795743,992753778,662334405,898591105,66547751,644331470,858133770,383852204,45194888,953634340,451790389,35435573,671164082,176294484,351472920,782334083,359808887,681603913,407003192,308474522,7603723,590167637,856523182,820788033,494166907,43004507,677692576,390408896,140475489,634359666,840570768,149303483,640321280,992835875,172114298,818254617,154345160,196800449,870605651,865440961,645545349,327890704,443215535,852746349,364380585,568923977,818312619,63375050,878161899,921648059,897560127,418425432,284440679,542351792,965683742,752734606,907002124,875867413,694688662,260466949,453026551,251195555,827102807,503551288,117483873,880521254,699952443,892167407,469449264,962540888,119067966,52097767,370019264,822249634,237120480,771648639,229619983,680015907,259773735,620531822,964404181,958440491,109152123,333219547,193781724,685711127,638406068,670271563,605076602,213092254,714457410,205295329,381785483,281826390,107141741,387628955,224849215,6967754,866444111,602742426,279355497,508943810,343331898,979459326,793307102,455966229,25469363,826766689,657738639,756154604,3624695,470725288,231276098,312329365,236455213,601085495,901161015,894650449,114049054,362928234,386979036,997816103,289805123,737506189,14162538,62659548,506228345,54273740,609048943,753042874,344492349,989024750,366746787,394987571,778983779,851727632,210337196,315177422,599368778,25977209,991853918,994609967,575349415,973313674,49389215,466403812,82441236,289991756,855143395,698308420,188880105,436428039,492881183,408723908,859637374,808369065,505825384,951452262,500512522,49031023,260616058,412675227,29878651,764975785,713258160,766707885,905773713,803331189,371429170,737331920,445933418,187935799,780699748,660234457,923333660,163125870,3991476,684624305,80563352,804861409,757901773,815797860,364058973,553952872,83868974,354103106,817729704,877658636,359056292,682873215,293714317,344608141,872372077,214537860,217298111,938420095,302862755,395850518,113646516,883278906,19270208,31342527,844172795,187697925,176966527,636560065,258450659,949978853,129724336,954913,950540131,90605325,186631946,226981711,105359006,181835443,245338485,686744811,808138529,390019735,629602874,437310030,73691665,970863349,10430738,300281827,802245045,96008232,906169092,706334445,826784106,937262209,58085060,304794421,315103615,975683542,282183879,301612312,300834556,567473423,937290323,801586457,832860641,714013813,708233401,816547758,311568885,962305199,636346220,48160594,525040405,790758484,407154607,342774550,946149627,156959265,841250413,792270972,733904456,346966053,514349511,99984366,25454838,104677203,281329488,32508648,205004338,319090865,483562350,462880311,946781127,911773159,4283891,717681997,31503476,458983926,567255816,851122915,354893353,185438078,960458533,716425891,468399808,609153670,965785236,789059759,387255176,108224705,701918934,992656683,633400565,719576024,942140453,790523771,916291845,60217575,668677123,513047302,178909003,881482632,747296925,548026212,437155518,918951065,899946391,36670825,43744543,957469762,929269243,321900901,775543604,528255018,381350331,169838765,512634493,262044551,339271869,186968777,687740343,303338827,924265341,327625657,789825490,296589615,121000338,217147361,171989322,867046994,490484575,967284733,644960213,838526218,63126637,819577801,492741665,812501999,510950308,370290353,916660987,152233223,343799473,246311854,271361010,852694071,165393390,21985433,302780015,483975089,682610501,680128316,114644779,321935156,473979326,53102426,917041303,95249276,207172258,877643222,492897596,532702135,745391035,478657069,429707160,344857140,741626808,779734593,877891340,305583444,53635336,496442755,348421260,116164597,73903881,226879956,536841269,709515651,30514807,630057303,875410153,131384366,386541987,307321014,953786104,627500870,377329025,613973085,599685896,708543683,845486631,301196854,894553004,309986645,371930700,416322416,859917803,767790141,389995666,766570439,379943099,676511002,888140011,824619763,802932692,619700091,373451745,487012980,639054294,752243809,756614559,847645126,925139828,23001875,557583419,860551136,823495900,95460945,578471809,12029751,676216445,576368335,78835193,960033065,120815665,961431677,73146164,119895268,630786699,612866870,291993453,954958912,585347275,206526983,707764537,245423562,847549272,954421367,384826244,374116154,247001105,241289571,550507082,249360270,378750527,976517503,646654592,958797332,946033733,883122906,616017573,216046746,999340546,575014853,85104325,219092361,205951465,877002932,676290554,989326738,765080455,3258987,95568681,894658473,434360362,330810163,780882948,163787210,385914044,74434897,723091468,822439091,35784547,118654619,696559662,973737505,598245292,895487487,139066955,915276325,547380283,869544707,306032293,59434732,590393084,267469129,698611116,};
void read(int &k)
{
    int f=1;k=0;char c=getchar();
    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
    k*=f;
}
ll power(ll a,ll b,ll mo)
{
    ll sum=1;
    while(b)
    {
        if(b&1)sum=sum*a%mo;
        a=a*a%mo;
        b>>=1;
    }
    return sum;
}
ll jc(int x)
{
    int st=x/200000;
    int ret=fac[st],now=st*200000;
    while(now<x)
    {
        now++;
        ret=1ll*ret*now%mod;
    }
    return ret;
}
ll niyuan(int x){return power(jc(x),mod-2,mod);}
ll C(int n,int m)
{
    if(n<m)return 0;
    return 1ll*(1ll*jc(n)*niyuan(m)%mod)*niyuan(n-m)%mod;
}
ll catalan(int len)
{
    ll rest=n-len;
    return (C(rest,rest>>1)-C(rest,(rest>>1)+1)+mod)%mod;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        scanf("%s",s+1);
        int len=strlen(s+1);
        if(n&1)printf("0\n");
        else printf("%I64d\n",1ll*(n-len+1)*catalan(len)%mod);
    }
    return 0;
}