1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 //计算n的k次方对M取模，二分法
 5 ll Pow(ll n, ll k, ll p){
 6     ll ans=1;
 7     while(k){
 8         if(k&1)
 9             ans=(ans*n)%p;
10         n = (n*n)%p;
11         k>>=1; //k=k>>1  k=k/2；
12     }
13     return ans;
14 }
15 ll C(ll n,ll m,ll p){
16     if(m==0) return 1;
17     if(m>n-m) m=n-m;
18     ll up=1,down=1;
19     for(int i=1;i<=m;i++){
20         up = (up*(n-i+1))%p;
21         down=(down*i)%p;
22     }
23     return up*Pow(down,p-2,p)%p;
24 }
25 ll lucas(ll n,ll m,ll p){
26     if(m==0) return 1;
27     return C(n%p,m%p,p)*lucas(n/p,m/p,p);
28 }
29 #define mod 1000000007
30 int ct[6000]={1,945729344,874271714,728937729,488957151,213941567,621948608,165410919,130152966,477849061,70646122,104331417,804334677,112228257,406385851,373610584,959189339,129232103,596011761,653302265,502350404,254254274,23933464,200023312,437339905,838455202,353529507,181826790,268707842,918554769,361346624,475114772,551764204,264122255,348587014,339775734,190610810,147039338,576212642,958452888,907080272,897468755,485757524,926001334,253159604,720502565,795701677,485379561,512490195,62869610,44647373,170729326,181183678,223602264,14266485,546070015,669748641,266401585,722432477,844276843,806809752,215407850,514089950,48258832,388402233,287386547,184275733,39087220,221157750,796058916,274451201,551481903,468840632,654694122,349643823,123450237,466554578,613371117,104229634,534520804,340376885,53768135,665006362,362834988,113383960,458629513,877935697,990187981,24010351,477599350,491321663,619368665,730486899,302800222,248364522,617385859,136706557,988949479,681384128,140672609,39443745,327846413,353172956,108275948,378351259,482275913,432213793,904945283,871063203,757590126,541675614,649654378,339103071,153511190,307061975,535998427,953278988,315396128,629843192,166102135,623766767,9922024,962639966,258645380,484156059,75913669,837794293,574075634,404396328,768092500,903633183,512519672,44285819,538902069,621789723,71341556,81438997,28847533,40513591,849551327,716939958,942552133,395636757,409774346,383255288,612104482,95851638,696370843,884779483,524922348,220269701,390881347,114227221,395767320,614338019,380172060,180822541,691300228,891829295,967678016,701386253,162940737,994175698,908221589,19098271,438672588,631720803,573850469,339056525,473356393,859071294,949727021,98529638,168890563,563975847,7483795,276476730,39489314,514728211,87529508,963753157,380031470,856696972,158703490,515908206,227044626,959511111,993078622,80360936,888779384,323285665,543535546,550763954,601069950,458756853,717452438,141044757,197501322,634124805,238583278,200414323,553793080,66504653,42069842,722598090,913608032,740683059,742050754,961341417,612741304,91785690,526087340,214299335,290988315,920349511,650032143,826861662,655676777,832872230,243503280,428075391,780176613,762279490,958553222,298583588,683539087,245173409,561149407,172900450,994863083,373712992,577710034,676813275,65061172,354158163,474587452,779048700,252731521,513247255,63716789,589280106,300449755,843219077,437936157,617131692,778975010,166446598,341293627,939851882,377019792,974135048,18159888,617899054,824539871,922256819,904951680,298436189,877366713,763013330,69488053,73161945,968841940,502298660,815060335,585478837,52225572,617841877,964952304,864682249,537138023,438032312,507344261,611203109,211965075,510592131,253042462,662211654,306668985,993054101,886017682,550897294,748379779,600811784,662510825,923914254,398819263,459843924,563578785,800110936,890507874,833696238,67588077,662523469,355339772,897895240,326276953,66185485,707119691,543399352,359252814,343020869,435649016,326479513,313711009,180736295,933688638,341979700,832484396,852821336,938966456,327938691,897898594,514258765,67631305,832209634,147167201,933864871,764372915,290610995,894446445,552066969,955550128,899538317,98587581,791520663,371485442,250166899,386277652,850700239,24883422,365069578,542759096,393648297,338311897,998392022,963038213,184331347,216025562,616142588,243671535,922469047,642896156,173840546,617065897,502916270,399859525,626708892,203438585,794335044,466847771,485435744,176762177,370414892,387922877,421040690,506803021,831791096,536761402,659624740,205742555,354512880,992080290,655638247,441557017,45234385,602453687,642559130,907907516,150309994,959349261,667245533,336984599,7514180,293021893,527065808,716061908,183191397,64976751,577967909,833760679,814950379,238991246,714290102,902231891,437427307,149073027,103173270,685925477,694198173,725256565,71168984,261760780,55757530,112359206,436686978,516723667,537954237,916255072,34043384,456908325,881291767,146092388,189805926,498850664,471576564,977024064,502710283,230937450,166248501,100683033,725464484,750575586,525293805,107750423,541103694,100780834,184498203,767490572,317419646,113029816,182757677,138614676,694365799,832641460,450632411,301670090,972578606,809851941,356139480,741575534,319109663,491688831,946837771,820876500,944731056,441691410,439779726,878100434,110259934,781810231,822737100,122949140,185157201,147977057,78103215,98159640,570747872,913214189,526507036,614910594,606219102,234699129,882201646,184318349,623751699,220799331,756153289,390599249,416019375,679472812,608212465,946818526,676784388,848462543,701625645,631586665,279738981,507735946,983863013,797150469,667058957,302361878,11123699,265956565,759232458,630434107,603234456,651468455,184824418,604726700,101186449,24954474,873710205,172883575,299713548,965606121,589841373,782619807,545740664,94087806,846145323,99057958,275906334,98324641,712417499,506415720,153372884,988856645,995466415,137196894,296743168,461577383,447394859,350928543,800328411,359672375,623997509,289025167,258422311,586168764,714133593,295537278,650382172,140783549,886171581,956390396,255289567,255216580,795608020,678371829,996937306,387496328,235100473,649738138,898466097,407604566,529571196,854241604,278302571,998505802,446819056,674284500,819876855,166920818,141076505,198714798,612486167,700718656,391542764,645522969,999548402,477521930,505594128,951413460,665706996,664760847,514065631,101412856,896853242,846607158,200777626,574295366,319187233,35082951,154276754,661540946,477502005,725521461,655895869,355739306,678518235,192498927,173855439,165487057,456827891,29739781,258791510,428391536,531278508,763339063,168419466,868466779,365442496,722700915,698024831,661694896,590895521,463918561,314021483,842517461,302478861,688035954,232366905,961113387,828397927,320767088,508824951,735431855,426624942,591154618,76109991,328101502,665849594,385026767,472223460,891042862,342446307,246096980,406346591,527916773,998217449,259406947,423766371,70821164,405777406,55383694,177073358,520289379,953144123,598695706,882910945,148088957,127593638,565277379,746539154,329767227,652704430,458041013,532152689,943689273,198275398,746095184,296234153,567962117,585755152,914398975,392347020,605551281,526603889,299409566,554048889,207398267,231395425,761907727,542580836,511879608,477430193,68337675,420520000,90537136,881957003,293703031,601859481,982488742,687784417,778652850,678832519,41785321,569973809,659662535,165782945,800601868,946694094,798296737,530957874,155643917,78799254,840622486,223970795,8485824,28964502,945323929,340741737,34732972,603272702,607664609,673843887,72927622,72008879,956047483,777700919,664146374,919751340,24878865,460990642,148315028,357424860,741503968,317099797,829104947,566163262,167156841,600465821,697110956,353280563,96899824,252662837,7893272,120921870,514991140,889565398,248085788,692098208,933756018,425884820,645876939,21896522,887680365,852291368,441176290,66262852,156844282,636816511,124116038,842190463,966404243,788403295,940665695,989549719,828820601,250027891,298842711,270122615,174406628,2135753,46964343,877722285,279439798,165618275,192058083,45442983,312364959,141906913,672563513,989170139,871761564,190705367,121151650,442674415,781847041,760092753,473161041,775211615,133246058,75660748,105103896,314024082,699785781,135093763,341755252,356922254,545665155,516050961,683432858,554252611,980150710,3809442,280205936,618138190,143338978,788688497,335020131,301878323,399780697,432488867,731503292,78552686,970031600,634518684,501384623,44760617,805930887,940017151,197445475,720089820,203297800,544488568,323817708,248584685,735890324,467669218,62087980,905110436,891634369,10533152,23990287,611609572,542849349,924481418,4214140,12444440,736717687,401040098,157325666,367265798,451303368,161946117,507226623,459380345,866752949,897212880,806566311,378612676,64109037,642588978,48895787,519942317,136434876,29861018,573535950,758513856,146511954,726260224,399742173,745185429,190644678,862659605,284303510,93481167,54655028,557236856,907886262,184073171,469064478,587825128,561305691,650561892,494974250,427901529,127482682,377916374,510109927,601476427,61867544,242080407,336520612,817284238,357107802,831433550,401060931,360517611,209089633,445727073,273046955,399724590,819481328,852463455,937507966,711938640,599907247,439538485,872938446,909790292,180096711,650114586,529418274,560890330,882019804,509410348,501169449,344529911,730231156,858736987,621110787,4459667,873347202,696188165,506145206,73642136,147943559,379421898,654783213,956981417,651743441,639780318,78577382,593374499,830162763,301755654,792435305,117970707,932913412,832255341,132217712,628450721,227843471,107653574,884405265,36919433,120185702,713929739,355335147,939617354,328252980,400671521,3750430,291712420,161768446,204525632,110812455,655316736,810170496,495246572,411585803,110977744,480012790,837775503,421678299,537576259,215096702,255249918,999498556,551932245,400608941,789747750,660573311,224129758,960267908,823407521,663185418,71834349,194653367,479377667,556838543,30135513,434301805,554957759,766164228,423757881,77024851,446918481,86585877,167204113,199048610,165982142,29904724,116697346,136404554,840462862,989156366,172584177,788447557,850533198,955155103,112270248,718115841,395066112,581133650,802794769,427918059,178030850,977926539,732960431,699231435,65702561,976789228,525323070,86516285,991883842,476155672,748102517,322281052,655855568,406512465,964314311,364509254,195333797,846194973,949738561,886254842,502143379,589271740,437138529,387943507,470570144,725480162,669584085,390652246,75608046,254775915,749807458,399204577,389518587,676947848,716992238,919341531,597635407,280866713,144960231,434116773,916307902,416987077,890332575,250543518,711290749,609117110,101790252,341587080,760344158,527693811,318500054,328492483,720790022,212571117,361377324,531509358,751847974,886497431,858449169,934013125,788050176,850699702,248810880,44441799,642211420,705573309,24708499,697713950,120454565,987670705,829805968,155043798,809295463,198062340,220732544,344473911,880492204,2038436,944738188,276417253,611404975,432855654,786086830,154324346,797055600,81184023,352392093,78560743,769267534,188623471,891873067,597600944,635025615,228156015,549216704,38864598,63700934,642477540,375302266,953440571,962793031,282043806,539322985,25446468,117648763,169455125,120897864,87881494,545841159,771895116,136580960,157187855,776017848,962707012,39503440,910505941,614200021,949980263,915287649,666122087,746726358,34334955,352453528,993894309,483994924,554577132,632653418,231205736,526017288,531492304,858186711,658185632,437684486,388797172,87656439,143442048,977222510,51584599,676403054,21887037,310923006,569449572,657178857,87893014,437053905,104461171,554450666,43805303,795485481,873115631,247594776,770261640,330356539,152552771,437835910,140803358,470347487,409255424,679123739,102757226,735832872,881201701,977704789,997586222,224007165,273193389,457636155,92154325,448813997,857983852,42617141,742134656,65964759,531393281,17238319,830087579,254323836,723445009,930990624,479255983,91551188,65774342,279563516,679097326,179469301,702743798,929427653,814434172,330288556,211704567,283074416,262054775,754010164,776761179,132845418,534231538,34229724,195970213,657800241,755172561,364070929,365961326,741172323,376852198,395396933,968033538,477416299,564491661,709283428,489509922,905330548,723541522,780759864,134664756,792724815,963896303,567528866,844166935,169392541,680577839,171914778,957909749,211668514,82957327,44234607,117590458,440473834,620784373,14157720,451003384,983615836,874696072,778532988,476571600,265345981,698792583,280038803,329624138,151695003,111941196,514504079,820758255,233110954,664754899,137441315,570223850,194965848,360409182,739091511,33239113,935173903,390436161,424186967,393517525,153598984,33444950,996562973,747116784,475741089,388402463,123164340,252744207,45683619,286149821,151352219,253348457,141215346,266674334,955441001,567007829,395176771,77581436,856850141,544290627,30091875,849950577,392214186,201596847,789966079,291632986,634087056,367465808,923890692,714154326,96395067,14462136,673997336,58048965,143620650,986057005,738602909,676856554,262658375,881073550,735766624,101600085,562793177,755867698,611633641,83001444,555445968,840211632,962912697,536127393,413177670,629812280,144402004,895312763,483303557,617554985,377341180,919868020,224757310,692354129,338976285,123095596,925293996,134174250,705551158,390400479,514039691,44359150,258684627,710602795,306364191,381736861,627472181,656170231,931322351,120602560,691837679,187119332,16726777,202984091,56859736,48373380,741653736,154736306,941819960,244682436,810153781,438809981,10776833,798074778,738964379,722270935,527866427,35177978,868149794,690506771,13188734,33748791,759403473,332684799,759456692,400505841,651619221,305211078,306719869,49600531,284379031,698176697,271698007,295342551,406973798,753021319,976471593,261940372,12785345,124617930,221763912,683402006,382633811,883800246,730897031,776117466,60563,149264352,869189868,111356869,953749071,722568957,819523770,800957876,929322647,528022127,874685768,603082478,934748494,976933172,892528229,556869197,636890668,608745675,416733789,648416081,952212514,95308692,619065966,771370365,706486874,752557136,391766815,601217911,207014632,873793506,903755102,968664489,860177742,817393859,656227158,194791064,224321827,532160944,339449269,752532971,181868455,154128541,723960722,62582671,656504834,728970183,769911353,685725527,731596785,243125725,710401534,491533761,146158067,27223577,635248711,487608280,894138759,791657460,167681185,682741956,509525358,678807444,365157513,563896167,178771924,176282538,278986827,360384478,795358537,322958119,70396395,458025298,583881289,677075893,949791975,126071912,137383873,884309528,718365207,496976979,73359019,994058135,696948974,343517950,790345044,221559459,331808088,342748895,465970642,693958964,936344042,98179810,191785663,699778777,195483637,124747596,612777425,442653810,67413099,881563022,753626088,610013081,527753366,891671548,74863503,588240560,845937766,261231314,603200603,975194516,513474524,994347975,651575835,501929355,364699412,617648981,548491680,519841671,987299190,49779092,355918972,607201587,571585943,843901373,944603762,340766612,622060979,268623621,236733054,800970004,746438109,779483212,984898,658762011,519244123,228048395,101476972,951247952,862532753,598205586,610767488,513429465,203744418,54342368,803818578,411937779,940805875,891345962,151687984,489664035,738916613,497305124,11731235,819921806,333331529,53110810,195781494,919569261,417291466,787817804,289069045,209459397,729576644,293180921,38017207,589692143,772826744,315763471,176047840,137174675,660073580,462390028,53496011,417640158,949880159,376242042,62820040,350726677,668420342,346340113,715695832,976716414,869036334,495375224,191994613,400301083,565256571,546000494,405489976,370391995,686936966,565374577,799690404,954023521,723405448,285855386,573282902,591651578,267533581,380567533,408520577,434678410,280173593,709886467,620244676,124424798,884241252,917414642,894828054,597778885,561301861,367614609,557737213,126347503,516713900,830137525,540944141,877974863,653952773,104309036,99626598,251630104,774443774,116677060,684359241,694927628,363560320,271329419,564565851,168758279,762553028,860880037,82738371,587986647,607030297,537216693,722516699,134253950,910483043,230169828,185338618,669940424,936477708,215196259,377412134,684459337,544922320,802523345,886283700,991672695,428110895,79405217,746449408,285945641,340151758,188688611,479132091,187943752,893929486,277347020,907336071,8801598,148425514,544354437,304683028,301542297,579182846,64811675,937696096,302896894,762947889,610036701,684448536,495614902,917359964,39429956,953378726,514890293,365364525,353855852,315081972,485238520,335554386,692111240,187671239,646151431,900294993,872955833,215100063,538326373,747956568,869883311,283019931,421932591,334019153,623723143,772843627,372230720,924112372,715621383,388262233,145616320,526589213,435241533,673355053,418806084,185426635,874930897,691329167,442722546,875872721,888170350,922986455,538343543,410668733,754255671,846675823,294948401,371369330,505219998,649902153,289318937,5325123,195549241,818266252,150310817,999603535,908394618,534051232,181234139,41440947,109219911,769119001,466791907,315175142,209636227,635302271,563818289,645741869,854997274,632350959,846070556,703203217,979845005,189611283,920330430,358782611,411747557,127420985,1731686,441419635,228747790,430794120,974817926,872239119,372243401,169055107,704740598,340463854,530639099,104489553,426173023,126833859,550897532,790122866,702329854,881096015,258357927,425083553,706110265,145054574,780168728,529404782,634212915,574309424,951279651,748247372,6607064,987370950,669387800,310511775,191716745,781742917,803272884,972051888,508422642,681377569,316957791,937861485,715403101,123776679,62268427,540897397,681673400,381997385,16895340,303189935,277465352,339141348,358702268,530282274,33804494,690807846,857272710,695987344,560090103,442754959,176733815,596918138,863111632,323500033,660520000,802864748,321010407,868649724,412866509,743659365,535707772,532385320,634841401,785605876,381799910,385504220,270003884,391390785,298234565,832097756,378468904,481794414,977562594,278907556,197892581,341211439,453849807,875756653,918090126,334676969,141724305,701871564,116132630,655728246,559804575,218508805,788889456,257123209,661333158,365367244,804611231,806193395,376967763,694077698,741791148,539548324,356308264,739814970,242842258,322534002,181902113,750317787,399757218,125433032,423098238,756353722,317322481,101293854,759308332,474334937,567894897,33557910,215658734,904153474,676810831,190405703,273841261,7189413,18682264,135490682,912451420,541032841,490202854,784075168,118151537,210359019,965519456,460254543,687592794,361474897,679163677,609714394,49310837,140987543,660106334,287980655,927669015,772448169,595395618,342603939,163346202,111741807,161810625,819733686,398709000,13558577,904544228,437444887,796425083,356554020,813997928,258057230,998351456,125012568,281432046,781159719,603931681,29244569,114290896,583078136,346919510,328687538,258283205,809198665,702335378,407803377,250521986,449090584,117804818,642877262,631243953,207670815,745251183,572308478,19776233,702920053,887470458,862850719,482216497,271479131,482938661,994917105,909138967,932246575,476219981,255640549,935345555,866191257,881268093,78207205,281963941,77277230,946233635,195498385,630396840,879031204,232175064,524339158,845471443,67773437,376521765,893370517,398994797,44556217,968773065,39822146,318514113,323196684,292576693,407521342,418930814,78427289,506775733,810282019,592902024,301284364,466214963,788393648,226090650,470665656,903177067,683713694,15942769,190964997,140375132,486045118,240639674,764736375,751862964,398037346,446284839,585325403,629791317,979124396,411169672,740127483,183365010,414881665,721612895,410639722,718634960,695946028,686543986,435772518,423020580,716492399,680140312,178339801,943507804,52170330,557894414,794441141,582581541,80353276,878932912,139005516,38129050,319762052,860167850,827024816,809458998,445769694,510581567,352675851,150208876,258764514,488312459,601205604,224231917,607084368,349054338,418511607,299490192,121275943,108358510,478238514,990079479,396821759,696496667,710009731,838272832,106919534,279040174,553955659,699688557,309207936,960535668,102206371,123927003,991526163,30194674,990792648,271370654,534048653,446914918,10422032,753826281,356220143,11752011,492506583,740854949,545193661,885116656,379116587,95469426,893959097,835616953,688544662,676613174,251400948,806449145,291793761,443294486,956020991,151848315,491502191,507732324,832723611,950995280,814273790,343108010,782481151,558706004,922491160,352517029,825347950,358424176,434465391,749640888,337287901,333008192,567410661,799183035,129583600,904554470,165886347,477502600,955688412,768582860,85802686,837185658,520489516,106019898,439258644,306260764,892975512,639639576,933302265,780794853,425586909,248223009,516853735,460367965,598417417,162873799,763790148,148716251,624014279,716043959,479758282,396895828,316663349,409455697,806945004,26929708,783758319,755178272,306570873,126906088,455811142,571867863,783292838,958962929,964052182,14841345,112825243,405611970,646053687,295194133,500414901,691817406,679753528,306785873,67352407,954965293,129246866,390626046,519960418,572368762,212999659,126328969,283359594,48558284,541800393,841155999,965740314,516553742,252264522,6794277,408404184,441076305,778729283,942586313,999295219,972154629,345458698,670964640,43773552,747716986,635188688,337779627,660865411,548621713,267133316,176700366,123639550,504881296,794438242,469971489,835957091,206865149,855928411,215053762,516028947,612112007,584032143,84191990,414793735,662664541,297971235,276971686,144790244,526498714,526041494,563933329,883526197,777348056,317939119,374479619,518490745,738227593,206687787,179406130,194737025,342405123,316373229,510033777,384349217,380957994,777389078,998623789,506809699,805498229,671829209,532721711,400926465,831530693,365209440,436572482,63021776,388095177,437167953,964658261,97877735,678357640,432526071,862840615,173168566,935166233,379951830,704014951,221884692,94981898,26622527,371832905,181076688,452101787,819105849,390710957,259385969,212288774,437333753,535102228,770233380,604502861,363699059,438838623,975366676,756010571,397674040,519970640,889530245,33058600,402071653,431651934,777645448,265724668,841136241,324237314,21220669,560984775,188245105,551973960,134755581,513071494,808628778,920393676,608754990,702168621,604150906,577508620,108970468,473210279,516444992,667196034,204020538,79949989,206339509,871030138,121751390,826890129,519137818,859020268,137736905,441886187,916710831,379326425,17279814,836600898,731459049,661876060,711316970,564894333,238281359,775114394,804070810,10912558,516093068,437439631,345291955,935200798,42107215,91710989,203145770,463103143,210013750,655206224,279200399,314148199,366824743,604019110,534813085,202486387,900303981,18611677,105748275,267622867,951799145,244857533,700690308,228677795,646576126,972849633,544694383,795557269,422838887,789759552,881783843,723520992,380909220,841105108,658849644,235377416,873739126,487980290,840282943,995631433,380126304,410165090,983145635,234043088,78416266,664907787,182114202,915072259,377932304,933995086,151964993,427776483,860666359,630340083,371210642,109889812,990700355,972064041,832661322,73240051,257461650,385534903,381108321,360610663,429783083,45617356,582009067,231460331,381683808,338989165,989397082,60477957,383598643,124136477,250331837,880601960,454552748,516489315,613110748,901538698,714665298,544164320,455895485,658966878,102307528,536581273,135553049,435472099,479213253,880530616,568383504,376182138,151824970,755748452,427820902,999851602,432538402,595028291,831674623,608956354,422873665,305130709,420479247,118481489,129400969,76592367,175758252,771854086,224539742,597631779,777457394,810870373,667921797,177100392,604790050,501372084,43052085,69374820,931723258,965896687,815232339,951139080,764690612,701473755,974762640,202471361,489227471,373227512,313093728,675599115,316609987,331323077,114513298,168979965,612322930,859506620,634056734,469023150,595791826,420911553,617094683,713801012,480413635,740322135,813161547,967803675,195890321,919945995,581830727,988021353,800390755,554461880,963148058,729208205,984785435,381930988,454570601,872709744,601002842,457264895,278673802,692175645,170024131,874519664,235931749,321144673,902733482,809834866,743373301,172745630,189236974,410048918,49363899,567319671,767666108,847636493,121078766,169047658,941029397,809284147,94152177,460687189,427099178,218654976,115937770,238040958,561849554,17947948,629098113,310235990,133778234,418255766,707292290,12850424,950081863,443221305,358355536,336768926,641298131,248011481,700792525,495740172,767791386,223792156,593749601,849351166,825869962,998521825,172995832,370152226,935374260,867976695,812436941,973803897,323995701,88294379,39640319,655116039,621777913,758684077,525733979,57146222,654953516,602988526,83411320,961637678,844040225,701824078,33645294,256769937,371811587,136270809,235656289,570621748,585555070,106419473,909204144,796990603,497194622,859203199,58570806,298812224,492707915,243534032,847263144,821669289,159862900,622474548,554301552,369983503,529364009,129591078,346995508,421977912,903786849,334716236,846115569,170860391,930282498,87287136,711030914,417833386,403664958,195356222,452848532,709030843,64054460,311227961,606255066,36280198,512198888,297497724,489005846,287915994,446606223,729803652,920876929,78244698,952570693,422758777,304898985,487839491,535104658,74200820,366653462,943891735,712269220,204194246,514729312,705567961,496369618,320852418,364372627,52512843,394630446,928475359,252156207,332332477,107986504,809202434,874289576,510616356,63987247,566049087,220211502,704434983,334827698,984845247,912203895,623414266,750554459,60185923,981874551,964547973,405237201,85270129,240887510,627356722,967954248,595612956,747341918,564052033,794400306,762007813,983285445,749453970,652575751,576905910,79525766,424628098,839755187,671650470,824330988,152104921,24864093,320332286,105682755,287988006,92816301,280233894,488100289,191031645,183533467,26064879,498865030,451315762,562771694,786924999,993564473,139744483,189994745,993245331,816497523,577840454,284351701,593833765,772706339,305541068,698814681,886186385,991350290,420935457,810658909,307810987,305484844,457226034,719330048,758527242,748299912,813117254,90610234,283331832,174331253,110098681,238725217,229282699,756096509,310256755,955046227,907184295,885753268,190142698,934656314,211282288,62960344,969155598,411579923,146244866,685737123,147047304,752708503,392007640,643508085,67358810,138618356,702699079,96503241,341189123,207051429,971956205,275822677,354101924,108106840,781954251,63192132,820302284,263963966,998186986,319257709,212458513,157931098,617034903,783703332,82566792,524847882,559628783,469915873,119370104,865714380,920749052,953618499,833334653,207487481,304009724,846356983,566206809,530743078,886832119,723829515,161675654,225367905,552600372,399639454,466581616,506285489,757526010,789467455,116877651,3198563,972701531,447552895,26689640,583550053,46972599,323657526,858466943,441805712,823851416,323076515,493984166,288310233,240957039,153433462,520860402,375224473,489832057,520412275,653655464,521145723,795517085,737845102,626442696,445706071,937952630,790138346,877209125,792061351,561454230,943825300,696333493,694688176,269459521,645662225,978126821,939791470,591934333,187460720,855461490,708910039,364871725,679996535,127300868,309911574,349847476,254970020,848342644,77531144,230106039,794429682,816816162,534730535,255229566,104936921,801456482,427384349,457735858,207131499,560905133,951875973,101844421,19087433,124105506,894638565,519853312,406655819,64124925,838409683,403820241,252699993,105839032,419487833,726836010,5074849,381972570,921740870,269592495,465904515,143631035,989488445,183234984,690953384,869763634,595692063,730533058,164101179,303930162,969819888,990596286,683139777,435118571,379397332,890047992,548040850,462928991,822028742,928824232,369250935,497309322,849909259,650205902,398024402,158271135,346993886,109872621,653933292,335983238,207572367,813182991,447470527,301492013,575929914,723218291,300698702,839846891,64295603,245744339,953775686,744683559,68412707,65229509,605759391,907305034,437154897,95455119,261655710,381016324,234367847,871675116,71645146,611656055,29949913,801478963,206072134,434065833,179944799,49493051,690923748,34291818,924475301,281235187,737771588,785161291,480067993,770422399,130637809,586154405,475495357,457916572,386492735,120811256,706501937,240421050,808006487,440147007,803360746,654869046,203476709,786330614,331140655,706573240,884274449,2877923,507766074,249214570,437121480,548340257,382663366,109193686,839606751,870683804,128629399,876713596,406441017,666608174,104445512,150509426,719491624,645194027,361468357,51136665,159355065,536849753,356571730,147498621,110264030,941512529,648461517,172710077,76900391,234408955,848376014,22908662,412958506,550883709,285171652,875022434,707470159,971854192,167472052,356844720,604557389,945062125,264920661,694537509,950247011,152476771,353727241,61545444,640828554,227742467,573066375,414136131,511055314,88732506,587035765,116056523,408698948,118580072,142942001,946745364,567283352,124111364,670142686,301701990,25337143,895050423,474908121,977872138,114084447,326617905,971141873,205654613,829761396,341422345,630656452,253218734,144528188,798938853,813120647,697370023,79144315,680955770,806587419,90154975,967206003,939722644,38566229,742629985,976996523,790975867,884013116,240686739,768976719,149974690,752876743,193070156,91995887,728697816,455671601,228953514,353625890,852930611,490666669,946578377,629642982,459772260,968043658,643499144,634638161,119590395,887154093,739679652,992405574,272549286,887897411,915544510,996735355,361892226,563559512,664054537,392478564,669974203,690825671,456060239,340532263,519155774,585679771,282948323,172665699,92984500,740475469,781910350,800051986,999926671,283053993,504330167,97861409,596664373,188565877,729706502,367183330,477700109,207582492,525514410,750219648,41770067,762507223,705710058,140554549,238096802,598919606,307482826,650449858,548477400,965912113,204854939,738491429,149618767,152513600,437313543,339059563,255211914,213975502,975452145,471451961,976572459,175276263,321115275,9689274,75912284,272524408,976076406,826146513,336121651,3375491,706438737,650301370,806224068,393686664,775307647,262974518,849351173,389755088,641077460,910206303,47933789,738307931,529761479,37852210,739513960,189225955,478232481,454944017,84212609,608977735,56215796,115226984,497781336,400286577,312107168,872122292,369653799,706177644,581114321,349073562,733631103,940176146,887105989,526651158,963256097,605590440,153377384,913340953,197888730,555107537,587379625,656324809,437439149,894928787,440942438,918255857,440659820,486778190,522758170,423200539,942184032,677313798,759937905,230468268,542437674,63070614,627932006,348752350,242897255,192510421,598616368,153548061,727252222,631461990,551343251,905622165,445648189,649409269,495991273,797514960,230618610,569543408,600703542,755267864,202240427,579032385,188785890,817908844,91205061,409954831,482570995,450452685,564253505,333792502,661073983,315158170,345340618,517851190,107783658,442679279,920636281,438653237,317325351,921313014,737357537,390087344,942829999,773473754,171557586,932805343,462876538,651035209,335362547,680898045,600073522,277823595,984758513,898569843,114371843,586713879,895700558,262382954,475054984,772891857,11397386,29593593,894716155,227064079,406154530,710287264,293978852,4213957,260122397,13350208,48324647,623400933,235537436,750135417,549561174,887510410,165029812,975170517,818634880,611208512,463069027,737967726,400496492,613215474,510388043,692101118,560766915,441946059,821799995,713718379,415674920,846252521,351986098,104424134,399813387,389418253,220525385,39779093,43244853,667166808,727372814,267273722,403214049,172871909,196746451,199002223,789766590,900672919,543493901,440100959,421991513,672574586,469988975,468354466,462087750,117289442,455301221,712259914,881156546,357265269,746804596,378883474,863154207,512155820,674635172,366165086,118752483,368037714,548529348,448141685,490117235,945744622,794815922,273939377,441497307,710053959,467503867,501382825,474580228,735674824,75282107,671387805,300831059,22368254,799825212,896574995,998357008,645722793,296054144,177782918,615658085,130625056,558958730,413796442,754635460,398204555,718306776,981106788,438910291,91793578,58070323,494401188,317979658,348017921,401023548,632360853,724791746,198802811,594133789,720100779,513405618,219743552,503808350,281835271,337961372,915413523,42583526,216148887,350481526,200308879,925670772,313326533,702118441,897662515,344934146,266931098,837042281,107347388,889563021,217539707,959551474,380047811,437861285,830456971,78583027,964369937,369357103,330171526,820431033,128204671,873636176,352024609,177320481,320429024,687940223,769176936,8373542,469771144,595161718,660460738,114243474,309799071,582036166,244320194,375938078,196472187,773662361,805604264,712921860,535177491,464002233,602505003,81969576,613993664,593440569,925667950,637195039,249011867,831008415,512198096,218440253,517727749,481582679,948842548,698116991,197618742,382172749,377557897,475327363,361922492,887655864,58279869,904516524,662050825,579642843,595359752,253244528,858116380,138478815,101071502,986994745,414656942,498312819,441538854,17610731,587337216,649169006,350462925,695897556,189252160,169688185,296337238,58201936,48125332,209332070,575634406,647683633,295118066,421745889,345605135,654234894,893699951,984414681,888439644,714358374,62737323,172081747,816370698,872563767,344451550,964782340,53024247,649365619,445586161,559876046,984156728,97931587,956707476,713349000,893248976,52324264,290195696,750171451,608233907,292167722,108089830,302311752,759620970,837037538,378716653,942077350,745909851,489169676,502638830,641986347,28607339,834873219,490706390,404379691,248930656,118913617,524670020,228423515,557803831,852987037,328006601,316511227,111964749,715406651,908154699,548194148,756036173,450030939,838034757,185827721,999808863,302851893,655256319,16244901,774040341,259072456,791997516,498120341,158745864,713374484,287585646,61571607,515625350,115740009,239197466,598377217,640262062,41930055,377961318,656993211,570914851,946667644,80972392,649593180,940343610,213854054,480964544,679670008,337549526,929236581,284549451,658750163,740096691,667914267,437336389,955656934,181249841,109703056,746495977,415654103,542846803,720440229,300764165,58031632,979548821,666915964,174769552,126365961,159972269,87281003,449059176,660453888,402146626,920544971,835032685,331615669,347473397,946568034,238019225,226719147,399338303,906380066,421083313,20966570,956012967,933591717,99431805,114230886,840709226,66910881,762402258,664147662,523962963,621910049,784102485,95133160,757477437,384680548,343098553,48079482,755482194,892821059,184302769,379979252,857224735,686627024,389849221,280233143,897485256,620614407,788693822,936777393,629982978,627435179,153154683,59817063,36153011,306333895,13222828,745073761,604285345,390968300,703182065,972338319,780133599,803301111,228808686,174902489,256302046,510077174,328238880,921501809,498606442,808562011,290860487,556980779,631000604,520309921,73750710,834713367,944371473,696180367,2327896,205809311,786318842,822784486,627572191,57279093,357975632,381848924,16882868,94196624,287890157,617677601,273456274,16133190,471848420,959926056,473604415,46182546,869575990,540614887,791849482,450029866,165080638,38408931,724378335,77310666,59591919,451980034,868890775,643635129,394634673,415298259,749206697,16022377,924447248,571852331,122452953,340479864,837139238,947497472,890182994,626868576,506673951,980265725,572888709,976342348,175282309,295837356,816880545,901551704,652841750,41238798,785798550,685832870,58571883,30155906,535319486,514234284,98021856,467803984,998400523,869828324,469305261,366926640,106214619,129812651,146690314,734552633,983187066,104667061,362307599,935010800,970946014,514005364,69502031,573881550,669036826,199870927,843234649,820478566,416601828,858988991,533598214,930405798,749390526,451899752,957066357,821093420,734352470,330458509,888670633,848295599,984127317,771028116,690220058,380591391,929269303,855013214,601991173,940438093,676549180,518056409,601666769,464668610,500980620,6651680,997906123,961209968,779082786,283416678,155859630,242434181,796349667,599512577,598207602,430402101,15770066,319996073,132954642,827064199,314065364,985782640,22697590,507327499,565172573,117885697,381447280,408901328,12773118,835630636,226555334,343320640,731722934,833162635,732260549,621846772,735203415,676796991,285015680,812110431,953353529,505966027,980196362,121093678,719026833,916221528,252813846,719728572,678262293,896043115,953755938,824029380,272931850,440406342,658122798,143787487,764187431,901946958,42239707,608094446,299608356,191414525,359487000,712421999,329007829,18845488,163124915,568983310,840288591,80681633,74911824,905091239,633677296,159789917,284044122,643200381,293654390,86468550,582098208,791517068,534717156,633221735,908839122,481973518,139692041,257475421,264112984,110339973,649193925,990186415,722732542,248458432,18838911,222107647,649001207,256283068,525483150,38222640,405399974,381547819,316784360,982201576,90368153,410042847,420080554,711134765,537299376,933873929,104632536,270686729,721760163,774238707,173068703,723383610,857007439,166447618,541032382,996735401,439153178,562454959,573664704,888376732,634748349,711416870,636757726,190665593,757573627,949872551,317655960,728263246,687234844,693181639,61435534,976441643,239865010,116320463,552915666,941471717,409656405,118662985,50812048,161287160,467013818,440841498,970802262,479790568,899728707,169378063,433131725,170127496,796598528,482789846,634526968,171259005,506008354,943174319,808031322,380695518,845179032,345273943,478170957,539282194,950766019,683879603,828709060,964879212,498178213,944078533,275943314,211404674,999092018,378562388,145723995,214567463,284836316,676826167,247248632,914427610,802883579,327732272,677673564,294099057,223335735,24359037,212609336,18010514,966612681,967027101,404421194,964135993,766066385,224677557,217557584,942356912,62875868,725638432,109595640,601524129,794031098,707777064,951847869,947477074,447313,553555495,852006424,317731752,265766196,782611047,716229888,793738134,694844227,861011909,325807461,467108780,984975160,604167869,14898136,311914728,982686191,154442534,769453246,302833978,242262215,828983378,32071010,151602770,105388511,909674068,476873001,348794865,722701600,888328730,977796973,633646331,461242243,243288422,794395007,286755400,444241575,324853945,540723357,873895032,548497265,381431598,984568796,849855787,371014862,936118437,536805187,798585268,907574919,756025729,780129997,545397246,726418303,672898099,65835808,680804561,186791114,978811129,826887864,781687242,461916816,982366463,783773856,33010580,897262835,500832600,229818005,593514335,123096211,629369809,65043059,713709846,142701557,636163884,195255219,754920047,484673678,383328799,354320508,504882608,572717320,280417331,772367139,55825532,569819106,115452526,719105582,980952209,408052354,342646827,50835713,907128805,540517034,600781904,112203338,291784158,900091878,737063690,61294807,425774764,583305717,15933188,205763578,935059743,654570596,540233657,514424386,677830931,981557901,926820205,418291583,318647653,710205834,237078077,736957665,89515570,101797957,538702525,878299580,736910383,247693753,279377823,850885008,825714432,868949985,836417140,834580445,870260786,116722752,420519421,207946443,297519156,89280285,501437919,548993274,830526592,110554182,310090817,249604742,791547253,701164024,299550775,956907633,164520660,138437687,125209082,330391329,132061248,537912662,789053447,2072295,353993647,208641749,697973714,240557628,148942540,357736988,620186408,958456503,987242376,461600698,608262620,154666626,786836915,502292090,271680311,294150300,475602433,687694837,362264279,450203031,898437894,931090287,662636358,644150590,130026191,513738870,426053415,864277940,742039048,26148763,208980207,30329706,73766171,831899574,230500322,69607515,525509115,410538536,963987919,722842364,304814549,915672813,2112978,754241977,293779385,876073836,488242630,376330822,27537869,786412977,611867726,749128083,646092373,116487543,236807253,532469770,913129810,807066747,89533075,304201340,639285018,64712004,643488729,7372531,85408778,385770151,560961434,731190369,616306269,855717310,670680251,422187472,127404761,297856848,865224446,688820029,701369135,360779930,118916098,887666865,231349497,142681375,756202482,109209628,690108523,305334512,988043328,167134294,429565318,597215345,906246537,608376678,608928398,629133276,934133520,16503114,945078662,197801111,991084310,77988375,725380794,151084038,935304793,168742005,350850073,613791565,540977431,804032332,745668468,849089896,647034182,532763066,102903949,522030824,845505947,507006432,412968449,669606675,670810445,602817861,9377832,879513622,804521102,783981733,340089026,561642256,578790680,155882326,567276623,696491411,624644260,469490618,696002728,921744205,113142394,976834847,285431374,211722565,918202213,671747723,876742205,798399422,410904204,7349449,467190641,461739348,62077289,552639484,635958336,584917681,792494315,318192573,536878235,169686952,859110870,846956326,202500381,85332849,778327415,938039472,570955674,110797112,730293055,273007133,40031265,815443058,180177598,484317822,435959908,968363085,667146253,990908903,86800217,142176740,703176479,869779052,421063912,971367714,684573080,706803909,70294249,838723288,860845277,150465588,492715330,727815926,87568108,703394862,533737963,466528020,541599712,894970725,14735460,11521712,354605242,20466643,866580533,205368232,363475293,272610016,209906540,902317268,516681913,838966797,519114823,40888288,135209326,774926541,71506491,238640546,920474967,181547071,12585478,925619544,68356889,374401326,194859648,245646963,184907468,393244007,690376793,619200167,168980909,54088782,769863316,799451545,223527832,76487775,282460490,673839144,68023102,225174788,717356010,79467800,673900717,551583841,355084319,736804788,826049112,377359058,518002538,233582017,325422651,692552339,789168765,495961501,658682368,589537486,705923459,585447128,300212797,42612376,386583126,565745655,395391524,302847303,293668340,952039511,437487710,778741484,780711291,658203294,508569827,908777679,69266150,647321139,203217582,390526627,536420732,583000649,983920618,24435438,361177008,867315382,305834007,722751952,613366477,346038928,445938712,828632315,986831110,151135289,263971559,649577211,19959705,124639871,585673270,418963726,963961131,588099391,555857855,910873683,540622648,747368378,935673954,934831608,393811207,922663478,27479901,584930024,320514146,344975472,277426892,669145954,513906703,592833703,483945514,692460975,702582560,184108157,535512258,834149978,119396509,813537857,48132512,971585282,187091224,14614510,15933679,721932133,970803416,728269394,361872123,986763384,734580196,863197629,990312727,747259143,461457878,949883267,419216145,811517868,712490726,92867639,159178317,960151449,110335930,693268587,503568691,651823877,908011256,876857178,175593891,963847566,68851294,457757477,40644606,236499432,745815923,477522232,518348702,329704322,111986238,66444387,664925481,164991557,338296943,399513144,503096456,406664943,108005961,414059969,656159373,863701604,879950686,864106111,599773385,527997941,607975525,44580271,483252292,660837233,785997793,241125697,691265059,123037914,286253561,213160974,450959004,875020907,721974689,593489542,665001414,905197581,456080214,325412294,686513090,682392342,471100819,748611259,783672080,664687385,613098019,82701766,247051132,940988662,699855854,653160599,253589170,454574426,648632475,561229480,439013878,780463812,751080642,475363127,872955171,221419431,660718935,616253276,620991239,322955474,95900697,736953117,435364733,400032675,143150458,892976596,778936048,870114869,693427846,916920202,531290913,159313409,854027823,956895320,431001333,958032952,435621676,147281691,782644049,363417645,788629073,318986652,45280716,627497306,862125833,55176692,769605990,50913091,759547794,415399356,91873313,435971457,972361711,886131838,698360174,778537252,867612407,363143588,210628827,227452019,167347791,136481555,794414626,886837851,833212071,867100102,962413595,506550918,150461107,97396199,322574611,286566460,418048639,126619502,49890932,424873463,577636888,598651314,214771282,633007716,67600639,872694032,899190404,807799524,536389663,783650145,198103723,406176925,596091368,865801146,255660985,950263612,204698161,570789483,35674858,355559169,627978911,108585701,612463851,227550456,44549978,430769857,197325621,365494994,215296621,794175066,165486775,239680547,990696203,54536891,267132823,879937767,468746039,925979058,896931201,784849771,365504305,221529004,715124186,598394296,273404498,942530408,892470275,339529469,637182412,714030555,4591038,747727171,993858038,98351859,587568276,635308938,66381702,523069101,611647432,93089964,621299142,87170109,91184576,582205309,384761096,623784317,274148172,565367846,707139350,413965784,111585803,462251445,228866268,199084146,547319848,912054783,776081313,50512733,398666776,860515976,132645483,784732014,283636962,567053755,762371460,902545259,6795752,933181225,79095380,382697365,79944172,18195218,904541583,983398375,352534501,206544638,590062152,870793758,26235371,885333891,755593357,797697319,233605783,916638079,592465092,389607454,700420311,196459900,86420454,160839557,696575,569324134,807071644,759233878,743587997,984681992,941063338,324982757,676014860,600520498,188292161,129801562,413126752,313832643,937070759,97526604,541466777,603982189,77969188,347408805,311339522,716968535,967397279,253173933,37355703,352327793,883519616,967973262,117140785,240224335,807324871,845415681,840729498,935684923,155577573,734434833,191517923,654123163,637896624,852058670,173168370,730184794,50915735,324841114,628137110,205149114,182695122,548334792,230832142,246897375,673812822,774458235,12653594,589139188,823592104,141584849,661263989,634220976,838048410,865644208,959538649,496526723,706515642,30364288,288996675,618298630,512675413,255909709,961226649,196140093,464842799,73771491,907822468,820941783,633421126,938423057,725611016,889132555,244245553,600535214,454683334,918501588,156397960,727549083,462344797,552581171,951585647,331017637,713844297,201014346,220893764,942832265,205089583,855055766,558242708,467800323,544040124,5018684,600324086,275710404,942082597,882387855,283394592,984698042,699687145,218659340,671476043,786242938,615660310,451633451,264041371,62057607,615318684,358229710,600528374,737949511,309417464,928413938,485704507,508289212,335423875,674380863,518017044,336119074,617416674,485819110,941096637,929311054,597002446,973475334,265580872,563517784,251569149,148530184,95396816,883600979,282561244,840871566,519908445,640741041,421822961,632376045,139437876,790411904,591820303,741935921,948651905,366299783,716525381,15431695,15465625,971346451,168728596,608506519,27394837,851151360,602776233,970664278,322046939,511916124,340275737,1956214,363111458,481072216,658163046,518552634,132664065,981823198,216243081,159795020,767941105,457986980,858463537,976190745,171187323,572871813,647899578,408338249,44147207,156374207,940179853,58043446,28385650,424517633,511617049,926045094,319879729,514748429,614317869,421026423,671332980,6835612,938930076,458303594,925057217,380172144,417162197,8078854,424003560,2008065,807569105,429700641,464740805,457368858,589073747,394260986,391506131,929826825,432872648,690774587,357406694,692130031,273616783,445027156,511488576,31976171,170358186,20482390,918198464,271438684,749710986,389073776,939445726,23455846,956187346,748137028,734748051,303817400,94204386,126522637,81942995,832809073,197225686,406203721,149560387,711052519,501674175,547993890,871374386,551852029,842913905,11301805,658024191,322045818,938590456,235068927,986201888,729075821,230293940,88489051,430417352,457640653,512463037,164939381,78855727,918299124,19019884,318003658,964003586,887976673,465062825,998287188,345218097,418436509,423868376,737852682,222443100,431664080,191790675,179137865,240191988,426955600,372855698,834981397,769820197,12457840,592849249,301573725,529831284,455945822,908361093,348036200,725019234,272002918,302014486,868309988,267131588,110362906,658933926,714755636,575129133,572255614,242451399,460854477,379734453,261883330,173252303,205271891,875823576,295295415,344691305,88281196,291229175,339458347,199662270,135955543,945346312,464533492,871840955,247580453,899980261,309580183,86978522,845735069,219736536,817617603,405963484,880265007,291366034,314006019,86753505,849126155,994666022,724217006,569965800,190010599,920028225,755930223,376881817,18255664,401402435,819561952,810240409,896675374,5648890,14322856,899043492,141273287,496383310,791004873,659659128,952106154,219105831,176538445,879815182,445593480,150528189,94493662,797589952,732282876,567925839,796782054,629643845,130694449,475573885,497611040,499200426,183468775,892394136,17028961,825354772,382036602,10367014,453970224,702396666,603040526,616353655,902691380,983386965,692566149,247825935,66330622,225112465,895795849,52320773,155947313,718224149,164300545,677709978,266340441,218514417,204476400,286595553,643512303,598766962,788301683,892598856,520036990,859133788,979526775,296869156,670015326,164319827,647208607,679949247,172064170,865163183,337039103,105046080,579964945,123270759,385113924,576031432,771688525,704910535,414466742,609386035,928631412,485368568,479480031,505949447,116422341,568991478,93574014,961174363,735174682,235632013,19234330,650946685,144392601,510837538,567469814,856042956,806198989,116886696,207340279,223268817,253945420,584643811,616483622,711150993,357748602,626063923,607222114,600586776,28542569,796083795,549421818,591429425,607254162,355391295,492527448,847958740,287070353,814226472,643144229,698819990,177700395,611101671,490661583,275559707,950224920,844587825,53229930,339523379,979109376,126378471,444745387,726629825,351823753,475484131,518938465,963071536,84665553,643867081,825793617,408943841,879707301,471828659,223598556,384354814,153231894,188992442,483627866,255018189,675911377,500327547,638084035,486199656,903986764,949245648,862319148,790947898,142578126};
31 ll Pow(ll a, ll b)
32 {
33     ll sum = 1;
34     while(b)
35     {
36         if(b%2)
37             sum = sum*a%mod;
38         a = a*a%mod;
39         b /= 2;
40     }
41     return sum;
42 }
43 int main(){
44     int t=1;
45     char s[123456];
46     ll m,n,ans;
47     while(~scanf("%d",&t)){
48         while(t--){
49             scanf("%lld%s",&n,s);
50             m=strlen(s);
51             //cout<<m<<endl;
52             if(m>n||n&1){
53                 printf("0\n");
54             }else{
55                 ans=(n-m)/2;
56                 if(ans<=4999999){
57                     printf("%lld\n",lucas(2*ans+1,ans,1e9+7));
58                 }else{
59                     int i=1;
60                     ans+=1;
61                     for(i=1;i<=5000;i++){
62                         if(i*100000>ans){
63                             break;
64                         }
65                     }
66                     i-=1;
67                    // cout<<i<<endl;
68                     ll now=ct[i];
69                     for(int j=i*100000+1;j<=ans;j++){
70                       //  cout<<"B"<<endl;
71                         now = 2*(2*j-1)*now%mod*Pow(j+1, mod-2)%mod;
72                     }
73                     ll x=now%mod*(((ans+1)%mod*500000004)%mod)%mod;
74                     cout<<x<<endl;
75                 }
76             }
77         }
78     }
79     return 0;
80 }