#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pii pair<int,int> #define mk make_pair #define Int __int128_t using namespace std; const int N=5e5+10,mod=1e9+7; int f[N],n; int prel[N],nxtr[N]; struct segtree{ int T[N<<2]; #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 void pu(int p){ T[p]=(T[ls]+T[rs])%mod; }void upd(int p,int l,int r,int x,int v){ if(l==r){ T[p]=v;return ; }if(x<=mid) upd(ls,l,mid,x,v); else upd(rs,mid+1,r,x,v);pu(p); }int qry(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr) return T[p]; int res=0; if(pl<=mid) res+=qry(ls,l,mid,pl,pr); if(pr>mid) res+=qry(rs,mid+1,r,pl,pr); return res%mod; } #undef mid #undef ls #undef rs }sgt[2]; vector<int> tag[N]; void ins(int id){ int pr=nxtr[id+1]; //cout<<pr<<' '; pr--; pr+=(pr-id);pr=min(n,pr); tag[pr+1].push_back(id); //cout<<id<<' '<<pr<<"ins"<<endl; } int sl[N],sr[N]; int chk(int l,int r){ int len=r-l+1; int mid=l-1+len/2; int cnt=(sr[mid]-sr[l-1])+(sl[r]-sl[mid]); return (cnt==0); } void slv(){ for(int i=0;i<=n+8;i++) prel[i]=0,nxtr[i]=0; for(int i=0;i<=n+8;i++) sl[i]=0,sr[i]=0,f[i]=0; for(int i=0;i<=n+8;i++) tag[i].clear(); for(int i=0;i<=4*n+20;i++) sgt[0].T[i]=0,sgt[1].T[i]=0; cin>>n; string s;cin>>s; int la=0; for(int i=1;i<=n;i++){ if(s[i-1]=='R') la=i; prel[i]=la; }la=n+1;nxtr[n+1]=n+1; for(int i=n;i>=1;i--){ if(s[i-1]=='B') la=i; nxtr[i]=la; } for(int i=1;i<=n;i++){ sl[i]=sl[i-1],sr[i]=sr[i-1]; if(s[i-1]=='R') sl[i]++; if(s[i-1]=='B') sr[i]++; } //0-e 1-o f[0]=1;f[1]=(s[0]=='X'); ins(0);ins(1); sgt[0].upd(1,0,n,0,f[0]);sgt[1].upd(1,0,n,1,f[1]); for(int i=2;i<=n;i++){ for(auto ed:tag[i]){ sgt[0].upd(1,0,n,ed,0); sgt[1].upd(1,0,n,ed,0); }int op=i%2; if(s[i-1]=='X') f[i]=f[i-1]; int lp=prel[i]; lp=lp-(i-lp);lp=max(0,lp); //cout<<f[i]<<' '; f[i]+=sgt[op].qry(1,0,n,lp,i);f[i]%=mod; sgt[op].upd(1,0,n,i,f[i]); //cout<<f[i]<<endl; ins(i); }cout<<f[n]<<endl; } int main(){ int t;cin>>t;while(t--) slv(); return 0; }