/* ***********************************************
Author        :yang12138
Created Time  :2017年08月05日 星期六 21时09分20秒
File Name     :1005.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

ll dat[]={
641102369,104818485,60310577,122646464,807196544,327677062,653842498,274708032,709905123,75821910,5775243,726541565,630044193,930509622,537185615,518384518,860692604,29182656,252663411,489189987,227118432,203593743,488159830,170423918,436447911,720765503,251142165,527712549,730470275,969446696,427440033,626629257,350719072,201159489,48412268,50566898,448285557,364553199,264446031,553783404,66211768,961388180,479274092,728614729,370483249,202228258,473769029,194780386,439485849,102003465,824584785,379467832,707266385,215074126,923941194,330696450,456450724,397674762,993357299,487845132,181582824,685679903,683174440,657269682,585830429,458948225,682657082,586370736,331132622,703390292,193265703,634718619,303428241,965483921,31429587,636936598,204094367,248363375,255514638,47886326,414876793,685431602,271612229,164069309,309284573,578095544,884350578,548390096,192744422,707381332,762604198,595933670,881428239,367468849,419203080,533573004,915035094,561745251,675087136,252318119,62492226,62050918,988741396,875341739,899580587,909930436,104925393,830337749,830508025,664540443,756536673,534388045,990119502,101825720,23526281,987088767,669403920,447489451,202249825,661968935,128816817,344224914,328642463,175602622,831463898,952440234,434569429,903871785,314620445,393166667,123766919,676509435,62794640,467967150,262136573,832084370,127763685,966636051,813768418,273353405,388618416,105484757,784885691,310722997,215720378,118666381,48242578,847749190,108513056,548153492,696528086,704359245,838747065,32443183,40297561,261804864,347105656,995838608,219216038,213962841,313657455,266980500,490520669,402732505,502746055,608863025,730294926,51272133,190867484,599065709,319518353,227723665,418002812,760838369,850175829,758896788,499498510,811549798,166321920,55153481,276850936,458120983,644607065,544763458,549415797,904317761,399456997,657985949,527272502,936282234,193558584,594702196,103622382,696456732,359624968,775278212,623134717,500218517,134185629,550706249,862847328,479938938,404593470,226045897,208473286,497957511,409229480,277122390,857468429,902357348,544749215,617440395,507967368,438047543,122307665,849046130,882477834,597600022,173441108,383383668,353373516,801138078,584709489,983230922,738720032,984519118,540657760,368724401,890303371,538102279,197601278,138155479,359807733,107786814,281136304,245495966,1119038,320330946,65585583,815452441,907465546,343681379,13341748,919564991,38400258,240949488,18881330,334074278,341236370,455967731,873937152,53020195,786073704,48502274,91883831,973954116,109960658,432293678,12000048,881675217,276896038,763887446,758326125,398998297,376698569,248109230,791543657,360860800,409081264,841784400,291020299,809147679,158673019,399553564,119254695,162995877,126090914,334614795,943535859,586719444,57814722,917194701,30820858,177088733,246270277,239734166,998785395,377095983,799837151,821805075,953553302,640575850,425682694,18238092,911086490,380992670,676596046,2266902,658038077,916643472,991837453,373382608,422658290,306827191,411596172,518895979,485985272,236414387,984628170,204487456,873026820,223232071,181094913,22864344,201374440,687290993,825942875,805978575,504929588,165761878,501107609,130812423,389736380,585477275,975829496,607197088,902259846,454174486,1612152,102482787,814174465,472915080,93176974,147122795,918054404,544120040,359472232,462635603,278367526,423225265,111527295,440109961,774578943,460191780,130297137,587630590,156573473,954637481,959499253,155520960,92804723,372623568,167090766,833586664,575203708,123842088,819210605,130442609,269188308,606512295,261496256,7868360,944144166,857938291,669394030,320392760,295822167,896266185,491707787,75610797,156365526,530455485,945481234,675738703,616958962,480154975,498706795,351628023,38179488,37991289,161778213,619852221,249688878,906438791,979446018,472201158,934687579,400960194,311936783,315358553,735807693,781870154,731887086,944949679,713755616,522576965,191414967,769581288,133088116,266758019,594121619,710286802,450388816,405131594,791556256,697093401,784156746,489190745,688163551,409319440,911265548,826999759,436426022,765776738,449309738,540574170,697914009,106315823,374480497,854277988,806651068,317234250,845896803,704503786,456670732,883183327,192904270,635721339,421894439,35435194,643036510,754090629,832271076,60873518,102168071,800649755,968060300,234954516,585412309,172764421,188188293,777732208,344510637,641415354,932032601,57032574,167534360,813123453,161377338,999575938,150119439,386696154,929968335,382084101,8024543,662177405,167714515,761630159,637480359,393208384,964710913,293376282,679121742,615338602,460957073,868333310,374842794,371841544,323684501,261025976,953841945,921457530,854388099,206419459,577458636,229998249,676259541,784201491,638639073,100455569,311626114,890189839,919279257,504426116,357612254,655201159,195380280,628859494,796989937,583570104,813102064,529775540,179683249,760619913,637906638,230455528,852446295,960424445,532749147,673062691,193323681,950917141,470857434,600694926,197716069,790383488,528964477,611072079,406988688,865822376,516744099,397992771,222465443,215415079,233955811,772702914,121569571,71793603,781757290,859212960,216025726,872871507,205816054,147016127,950900430,467524114,89938823,952158665,647554067,285561813,90827232,223202808,578796645,615274402,138589945,221718024,292842151,986865455,896620331,563693849,833443259,335558214,86110950,138213658,308120313,577433386,797167504,629624516,28040941,280196735,131944701,330114986,994277835,182022448,132200890,178209882,582104355,96125953,38129642,312664495,703571519,366702332,258456725,339212053,158095,313985352,879397962,757222089,881746671,245062883,926668488,165440441,485535416,883191807,457311094,269867015,968853662,76587003,917996265,398871229,466055214,181043323,47479057,836006686,490332325,909308257,29384812,802362338,930579035,20739347,95442303,657757403,737779990,494941834,356992466,716722152,388397959,743882906,858605478,147670945,636839245,927388317,430810230,818840022,420607628,552793978,666661132,946543214,554388678,530461425,13370869,65201003,936481192,272325994,408612055,947668039,27463622,698386535,509945856,509790590,917560505,816184330,441126736,766081415,390259792,156058183,240036157,745371572,52122183,865945508,608621778,850373792,663928266,550892371,594123578,716403935,823772331,170895407,138994430,523884128,313089166,171479257,924901994,268773411,599702269,542804573,696487881,2105831,329224028,853926583,97892915,567215694,659954825,703774286,885114206,536542848,925893252,111805458,241234751,480795159,664237630,527057841,897100065,314199964,469914899,258130576,420902388,995112496,777318419,533194448,851116611,848300059,944316155,223993486,626565799,628221961,106579490,205813046,375027952,923972754,773963555,396701156,105142082,671226838,443000539,668426078,861043529,8845567,978942509,486064573,488727276,600590523,222836701,273253219,91630181,576113180,546068535,561540343,10792263,943129802,351852968,625767785,467817644,8961550,915858343,779290566,183712724,389209872,702042064,618417640,146232789,531324214,90142871,488269438,898956907,967672978,6167328,74937261,642748577,198972579,434943648,273082934,175251291,367586504,928560804,519172322,149410649,994335870,353804154,104800536,770837182,51374755,584996003,552080414,760085013,441756787,516463285,25437845,189938975,788939190,871699156,310099367,610363086,844405909,633788902,542030758,303181396,147871553,392280622,375462363,727439580,282215826,594449778,784170433,145360170,673629519,41069414,110042976,922217639,871131007,74678740,303601639,833911127,226443744,826899855,1761469,786816607,967035458,488943604,944037047,547505448,902469434,588811146,366691415,268999120,207730317,119431084,808903304,717076911,488948136,394246697,614204148,327586942,865129939,306196318,939406463,193627409,767323645,177184823,861924358,816523957,869099701,596155286,116414979,783469234,87130396,578657172,769966342,585482568,16594075,874648848,492097673,938631856,880107963,103872946,388006632,545900968,905991566,418163874,178145608,701644626,690535907,608386958,341611310,155505310,510196827,477430250,237674265,966795515,670794013,738409801,583629963,748485548,151264760,678180842,519795158,920112162,300138558,150235335,146881481,507052184,951494765,250344444,387447657,248322546,463069437,314980176,669754074,229163405,476666756,815334097,707168528,380654482,58252413,182323488,470643987,970826613,234233704,829459147,666582533,110940874,104407598,982460481,274445598,7024370,862831377,833221694,330372656,781208006,708026397,122874372,350324799,116636693,331996093,482042137,917742943,498352564,74632571,295841940,925405821,545551486,84834837,390506676,808158497,621817024,422659656,920015671,330795277,434229583,651801661,818633715,358902223,525553449,376747803,96019813,251735186,535724610,693007388,735427287,688986423,122999578,157079586,494403293,185157417,948168371,724746006,351302120,962227972,325372676,786913848,103492735,410650078,524679866,275672338,214845924,892604671,633552411,756726188,610166554,146454940,107743646,269236963,754541178,810235139,986276099,734104915,608296472,775810797,822995365,733789616,771865665,418405015,359994989,377915097,229855164,224411867,462111521,862338476,900441068,694346016,768798462,517652691,168217611,266820154,473146834,476074482,552182233,949313880,871690478,301063741,164172460,438405853,325496407,814037185,967576926,573323548,882385603,406088123,410401233,684062376,657732213,361533587,48385277,125876811,312330178,976635451,395046936,391625835,189136406,953226339,226454389,366744284,683865613,717176808,322111006,214918103,59829549,764616449,55714423,983319618,158186251,212543325,944741043,905206729,591973192,829383948,638364042,458918733,323895625,138472286,493435549,996433701,301288732,515415310,97031835,68735384,377451664,212120317,199349197,187046634,265414352,282808100,229822519,434952461,601094801,237157677,56597548,786308426,650703482,740087892,0,100843417,335704827,782099537,94456710,290137545,571375610,926740849,526950565,713972601,66341069,897575053,356919148,353558502,876205124,906510661,917653519,789981262,854822782,164062879,961102028,897440596,438175025,188723959,83261356,375473300,930563744,427560556,852443258,715173220,254652689,726692304,946029005,759655578,456569516,112059356,358102301,714460697,133222072,504718276,369901080,494134295,776044872,430111873,605731794,501032025,390945038,837638068,532281577,309122952,351682352,390892677,232931389,659183996,254336156,270421991,755994186,418374572,979053469,41885736,485480394,102263310,925430486,665140785,640846738,925958034,857296202,960214709,863082629,497475186,748683943,699975,617306647,797968458,171437946,630816591,872001904,737230701,915054534,782063489,293049634,162690593,943933246,419316647,3496587,267376519,835478794,757349749,664106243,284161724,777634876,393923770,351542120,854042583,544299685,805455231,558031893,89263542,563728299,706104818,760554487,962894642,596150797,666229286,584829227,931890365,535175514,329563175,421522832,635634115,238000198,373596366,12324136,848577234,59130327,200148194,25505808,860792594,717613125,177599355,729216031,276327052,561693686,828638819,32859600,70930092,118173202,749123421,480837481,15676159,800647362,86922992,682536456,633249645,6483037,331959376,916491750,440139845,212421628,580111340,311174591,159956352,189211303,775936468,106692328,286305038,63240343,834701519,164687350,633705821,778255501,358826438,867881400,334580649,458824996,906280886,189891888,578598296,505748009,401755639,140135843,926933554,325948016,872452060,907631080,952181268,827768521,426614925,477076146,597503811,826405089,617101989,280727746,718714449,12995025,206154292,443946059,377726361,299170941,274887011,182771298,16777384,913898131,387503111,707723666,549723008,879348437,362792795,597426523,467635788,816778272,526494891,614637378,357630100,377000516,234878357,863853869,558067707,634145381,838360516,183470240,249934073,539639513,4659189,562986663,86615244,572351814,315523941,386235120,169749070,661852684,738920267,406257155,983246469,985286270,438158439,950741651,866619690,727625096,35543218,582373795,911853351,294927717,387454332,326879635,760758236,821895503,252565000,595229328,140243645,354313765,460155965,982950174,493174799,863074590,433570857,515827520,926420232,750810766,647550853,499449014,859778084,851515806,247700827,730313444,157160467,681340953,263172438,380959128,430040745,669017611,532455693,844810197,775778494,775557023,337688856,137789193,311789815,516925873,921784240,766204999,339024699,304896529,463829418,93914126,154690891,524816809,93251729,922483802,157561073,403608376,671935884,848467911,357643248,980023484,252316733,588163288,216992645,824887162,95063134,433856622,330412591,359599814,349621165,353732538,630473838,596508248,155919754,138057958,280602161,877587910,444210168,669990704,289779022,403316745,864488156,84797309,442344816,520479705,259168262,557127014,104858469,130605369,763732875,106675105,325120213,217873093,162889955,618075833,86998258,993595123,741368331,260578640,639331847,764398580,881931823,161179443,671594179,100115871,933762164,751377985,463552671,412908887,416409669,446980368,752863705,452763810,878046824,783835083,794740424,804518110,634175078,937471960,841072207,672163715,808264319,842461989,83955547,882790435,998639005,388591211,73599082,628026259,785678826,398918028,921718579,765472129,610274724,646345158,759357299,855053231,241971567,530092506,341248808,207408733,516145632,539984362,932268109,289472903,195370867,264185428,466943462,539429936,746911726,182150395,734893894,219447629,250937952,234181442,909943323,419258837,210651551,994019226,688327540,631795828,770746640,329969373,554706655,678121477,815790019,722579974,301471405,854859979,421387258,483703618,659016968,840888889,354584417,582876859,634815817,756216575,355710998,287208447,114905117,397532720,51287098,540892951,485318887,725770240,785443467,484899726,250336067,643442531,722151668,873183805,975244399,685575270,512539562,187627244,151149080,552794787,791569791,794580102,524486557,804423281,4007590,99607421,934422784,235399918,276475007,240499549,699378262,601780235,738027477,203212617,227977327,891080312,246358235,285552805,940636987,556458849,172829133,34320964,184549691,756194636,969439243,765434569,370177240,160043464,945717608,688467677,820114512,37843750,328322387,277072312,481004059,34285955,801913698,666394027,227172582,583929347,731865073,575412939,214644187,600305356,653708605,204246041,173263914,687143327,538244779,874174202,329227693,375758967,132986986,844966291,252771424,375645683,559741154,373744549,461236772,925122456,257971025,454356787,557865706,891285511,443620525,657963752,294342750,377254404,622138847,932055499,923530890,672733207,508369761,906945963,924810605,804158233,720667124,338137321,758734857,553872668,115422368,43710617,190241012,969290916,120381197,235911451,733138400,345661656,279274982,166285431,593865934,624448426,949294286,140347319,365656374,143094682,44748606,88001764,253501906,995523671,287020266,741507769,596269713,997042303,587467604,930280846,754414236,7067910,194753583,613362457,131767172,257017432,97799035,255870480,911550415,378437751,920265857,316687389,888090458,351734219,933314133,973343250,540898969,101944579,648193255,860061,729129617,494316434,186647448,776077664,83575342,532717529,45911111,559232735,965221405,889935692,804639306,556959713,959223944,567428946,664559301,194826215,754499309,452253259,326526298,895143968,885487495,903334745,156349766,610444883,485587619,685652160,22708270,69484582,736436488,421525054,572219791,940638220,871411669,769881855,472603031,853269005,670754499,844870783,99864650,385102303,212671458,887488168,642735434,330358868,929894152,621505516,670398277,15019598,495554362,487553090,993187669,933579004,545990714,427687484,679628473,826729602,195504630,846657247,82007076,977576603,788393150,35329749,232658568,484853472,131434470,559926893,245026356,688723785,373196878,119519800,95430613,781922673,880999175,528158065,97388012,961079217,194537209,40907693,251964128,513303773,425034076,432226121,941602291,931177528,13816164,821818083,212731821,640068364,177781586,708852735,94051239,327980909,408715898,680598490,837034006,284929008,58057540,32708327,297026560,858837031,866748689,49348369,545885765,516945644,451403267,524066351,951985364,110016748,100085648,817361995,322979613,287068899,540197355,553594322,662995862,980691728,143705448,537680366,647278014,428045820,268295242,303070339,659828329,564894678,496046865,397825743,591338498,995725555,568645133,286361995,925750759,343027580,790323024,943596369,402908233,169033503,761525610,281330572,238172295,355307970,421168133,9583702,750459467,315856834,128442001,119968591,124617520,586847279,897623953,417057560,880418263,963390509,507575736,910343949,891714247,810941676,552399204,297247159,572771750,137738609,677262069,593620168,241015684,465975377,602595069,123044699,917224633,738139221,213798451,407772334,566922035,90295339,171103493,691016608,224847277,818669681,521669471,426197567,525915218,750927130,591142693,640139340,492469221,614376377,151779016,841306863,535037050,200502675,422675229,392252208,854802710,394413471,392218939,564366755,886290247,802782733,508527105,256470823,623764453,947393396,214604990,667916233,835550560,646519460,793897093,394291980,341315627,554479148,909978709,533507968,57279375,152818930,414742577,791109394,947638626,151649838,662948310,227177304,583996341,892915588,757009261,315002770,239283190,988219301,509527982,3935505,52999679,464481795,408306398,246648051,81867614,817308208,874186074,305561015,226801574,957474387,306842277,217676724,794672622,503348917,219976663,666063165,135153774,379989946,482288426,24453626,427955466,724665636,525209888,196920019,244148985,412927199,766523883,246078468,91878499,612586061,593907245,874502806,133526765,367377551,228503583,231862611,359118932,715860201,474231068,385383546,176300647,595825892,861200626,169741,358544322,991422984,496619054,718373006,930561518,591626133,703373872,933580787,443403421,221683348,768809325,35506734,501210685,730555473,734685931,559117855,172030513,364330507,133099923,533372476,151889834,271211780,716491834,287365921,52107612,450280895,92857757,991919739,261253088,552239882,801495564,76847194,198146455,418471975,156026368,478759081,63914465,693624989,841169063,235140551,726504282,375612326,935823678,721395827,593229690,926611610,942879229,586610462,946572712,886347378,998380334,843836351,132982927,590025464,389560397,61353664,304976419,504633265,137779327,899580324,4553872,459451922,975244512,501427316,463515939,941812216,13751192,180250851,487950963,365015640,678335879,579790123,609663150,928354747,312555873,768550003,645019170,803108635,743746251,41930741,388787324,843664693,34675468,886003914,366881159,726541914,521427423,383886093,708004605,340201186,567901633,952012737,224393727,235512762,808368017,161334938,154145274,689679954,218989071,302059044,763902869,810764422,856098110,676979386,135639884,71773550,374409801,582236494,938244322,542429927,219838601,768809680,97204055,700735421,153146861,296163782,487504153,54051451,7330677,395254234,706987886,108195039,296890313,378414833,491981621,892961110,11488815,156954618,13995098,243746504,521875678,431692989,297601020,623661146,647336572,272376879,687239149,287613146,679464343,701871934,917137731,813895657,687547253,555578243,350354071,86727430,350002561,673107644,334707791,37617305,278923551,357938338,348224134,222922108,600833987,650650882,791511536,550524880,206050571,153645668,95617766,703180697,166596011,571074847,531931942,110621187,302377194,966009118,925591879,767842399,333546086,482269147,475282770,108098113,547294215,529308554,185404339,572365520,275408878,399053377,573721533,429091469,563610102,322189910,787015130,306886273,738952295,794790998,390664432,372210469,895572137,935904857,514862672
};

const int N=1e5+10;
const int mod=1e9+7;
char s[N];

ll fact(int n){
    ll ans=1;
    int cnt=n/1000000;
    for(int i=0;i<cnt;i++) ans=ans*dat[i]%mod;
    for(int i=1000000*cnt+1;i<=n;i++) ans=ans*i%mod;
    return ans;
}

ll quick_pow(ll base,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return ans;
}

ll H(int n){
    ll ans=fact(2*n);
    ll inv=quick_pow(fact(n),mod-2);
    inv=inv*inv%mod;
    ans=ans*inv%mod*quick_pow(n+1,mod-2)%mod;
    return ans;
}

void solve(){
    int n;
    scanf("%d%s",&n,s);
    int len=strlen(s);

    if(n&1 || n<len) printf("0\n");
    else{
        ll ans=(n-len+1)*H((n-len)/2)%mod;
        printf("%I64d\n",ans);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T;
    scanf("%d",&T);

    while(T--) solve();
    
    return 0;
}