#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;

long long Pow(long long a,long long p)
{
    static long long ret;
    for(ret=1;p;p>>=1,a=a*a%P)if(p&1)ret=ret*a%P;
    return ret;
}

const int BS=2000000;
const int FACT[5000]={1,578095319,259081142,316220877,251368199,682498929,95936601,167332441,336060741,626497524,491101308,565768255,968999,638587686,19426633,76479948,842267748,485348706,544075857,798967520,723816384,721996174,323604647,398699886,294587621,67347853,196447201,228338256,762479457,811667359,27368307,59469516,766196482,86609485,340941507,625544428,808412394,585237443,361786913,595143852,199888908,579691190,459188207,439729802,899297830,888050723,736550105,85990869,56305184,168891766,927880474,934814019,567277637,44930135,47401357,281863274,692636218,14235602,400295761,421835306,661224977,168203998,544064410,583967898,751231582,623534362,243276029,60050552,395891998,159554990,970055531,487998999,82104855,513365505,1559745,261384175,323214113,444090941,80729842,664989237,195888993,457882808,212938473,827544702,677711203,66404266,195290384,349551356,83489485,52167191,547665832,350016754,296269301,23015220,748566338,109838563,105574531,542432219,325636655,630621321,933245637,238971581,557301633,848952161,925152039,724691727,238087006,910291942,492237273,834860913,368925948,740594930,806047532,172115341,116261993,268838846,243624360,481661251,95182730,115435332,136026497,710729672,366384665,270239666,79874094,112390913,103056890,339464594,108312174,479334442,135498044,591048681,353339603,839849206,736265527,217544623,618898635,380858207,898554793,54062950,419363534,160398980,990918946,450718279,648991369,500780548,39052406,460373282,461415770,643638805,668123525,673464765,199866123,841799766,504962686,128487469,299172297,577786541,773206631,204355779,30977140,363172638,472935553,587220627,793270300,522049725,335416359,472012302,332139472,464599136,309058615,580204973,954840109,895609896,836813268,386027524,724205533,715247054,830567832,68409439,189239124,943653305,811056092,825132993,985084650,148528617,882148737,701445829,302177126,241107368,940567523,325334066,115312728,218129285,180002392,917084264,435327356,421623838,59883031,79716267,429277690,316486674,940338439,940524812,833550543,996164327,697611981,274192146,925347821,893732627,358655417,581830879,347046911,125354499,247662371,568392357,209244402,149586983,309134554,263053337,780072518,990826116,155569943,711553356,451373308,462639908,654611901,41815820,675258797,934281721,275105629,325912072,252551589,554917439,754363835,909210595,719566487,424989675,50590510,198768464,99199382,747407118,497196934,726997875,296229203,703397904,732868367,26031303,216665960,352946234,733333339,459878625,16634739,68718097,404206040,97830135,31131935,864326453,167831173,718498895,608823837,385388084,681756977,313132653,442795120,256141983,636578562,553033642,919273670,326686486,141827977,693305776,186576440,565456578,519397500,696628828,370732451,915265013,923043932,777901604,637939935,490676632,462528877,798895521,699767918,811575797,606870929,179111720,508038818,752550134,848924691,34629406,435904287,208184231,206330671,131772368,648711554,523696723,25058942,817928963,724464507,701453022,281230685,596949867,303076380,272814771,48824684,939889684,48527183,484458461,326159309,668422905,965656187,359960756,407934361,456152084,124804049,920251227,483924582,167087470,903466878,368114731,388728584,249153339,322908524,92255682,15570863,744158074,334326205,98349682,769795511,888146074,582627184,919419361,986708498,373745190,256853930,702823274,308186532,180350107,606241871,273712630,682189174,946867127,502371023,825871994,701506133,341779962,815463367,49187570,957939114,933376898,338121343,869630152,632627667,435887178,129621197,827722926,918513230,547838438,852304035,689189630,567033437,212842957,404149413,663307737,206282795,488906585,280700600,534279149,375297772,922377372,219932130,701050258,863002719,217598709,810551911,247844667,812283640,857241854,624148346,564827277,478982047,454039189,48562889,671734977,508831870,897162044,892168027,277714559,624500515,808691930,895205045,628829100,919717789,748510389,574455974,172096141,581418893,15391652,203191898,880691101,986598821,264688936,785804644,423951674,696623384,161960209,541120825,841656666,629786193,269571439,76770272,421943723,751040886,672850561,493689107,100228913,639655136,929893103,814362881,406024012,10065330,983737173,551060742,823845496,946421040,842203531,894247956,885362182,116667533,241427979,281804989,563796647,774625892,256473217,918860977,753513874,304644842,161362528,627655552,799289297,816701166,787113234,701220427,245795606,10475577,759404319,491466901,114495791,586445753,718623833,66547751,351472920,494166907,172114298,364380585,965683742,117483873,237120480,193781724,107141741,793307102,236455213,14162538,778983779,49389215,859637374,713258160,923333660,83868974,217298111,176966527,105359006,10430738,315103615,708233401,946149627,281329488,31503476,965785236,916291845,899946391,512634493,121000338,492741665,165393390,917041303,741626808,536841269,377329025,859917803,373451745,823495900,73146164,847549272,646654592,205951465,780882948,598245292,698611116};
    
long long Fact(int x)
{
      long long f=FACT[x/BS];
      for(int i=x/BS*BS+1;i<=x;i++)(f*=i)%=P;
      return f;
}

long long Combination(int x,int y){return Fact(x)*Pow(Fact(y),P-2)%P*Pow(Fact(x-y),P-2)%P;}
long long Catalan(int x){return x?Combination(2*x,x-1)*Pow(x,P-2)%P:1;}

int n,m;char str[100005];

int main()
{
     int T;scanf("%d",&T);
     while(T--)
     {
         scanf("%d%s",&n,str+1);
         m=strlen(str+1);
         if(n%2==1 || m%2==1 || n<m){puts("0");continue;}
         long long Ans=Catalan(n/2-m/2)*(n-m+1)%P;
         printf("%lld\n",Ans);
    }
    return 0;
}