#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define ls pos<<1 #define rs pos<<1|1 #define mid ((l+r)>>1) const int N=5e5+10,M=1e9+7; //x[i]:i向后最多延展的R个数 //y[i]:i向前最多延展的B个数 int T,n,a[N],f[N],x[N],y[N],mr[N]; string s; struct Tree{int od,ev;}t[N<<2]; void pushup(int pos){t[pos]={(t[ls].od+t[rs].od)%M,(t[ls].ev+t[rs].ev)%M};} void build(int pos,int l,int r){ if(l==r){t[pos].od=t[pos].ev=0;return;} build(ls,l,mid);build(rs,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int x,int k){ if(l==r){ if(l%2)t[pos]={k,0}; else t[pos]={0,k}; return; } if(x<=mid)update(ls,l,mid,x,k); else update(rs,mid+1,r,x,k); pushup(pos); } int query(int pos,int l,int r,int ql,int qr,bool jo){ if(l>=ql&&r<=qr){return jo?t[pos].od:t[pos].ev;} int res=0; if(ql<=mid)res=query(ls,l,mid,ql,qr,jo); if(qr>mid)res=(res+query(rs,mid+1,r,ql,qr,jo))%M; return res; } priority_queue<pii>q; signed main(){ scanf("%lld",&T); while(T--){ scanf("%lld",&n); cin>>s; for(int i=0;i<s.length();i++){ if(s[i]=='R')a[i+1]=1; if(s[i]=='B')a[i+1]=2; if(s[i]=='X')a[i+1]=0; }a[n+1]=0; //预处理 while(!q.empty())q.pop(); int lst=0; for(int i=0;i<=n;i++){if(a[i]==1)lst=i;y[i]=i-lst;} lst=n+1; for(int i=n;i>=0;i--){if(a[i]==2)lst=i;x[i]=lst-i;} for(int i=0;i<=n;i++){q.push({-min(2*x[i+1]+i,n),i});} // for(int i=0;i<=n;i++)cout<<x[i]<<" "<<y[i]<<" "<<min(2*x[i+1]+i,n)<<endl; //DP f[0]=1;build(1,0,n);update(1,0,n,0,1); for(int i=1;i<=n;i++)f[i]=0; for(int i=1;i<=n;i++){ if(a[i]==0)f[i]=f[i-1]; // cout<<f[i]<<endl; // cout<<"!!!"<<i<<endl; while(i>-q.top().fr){ update(1,0,n,q.top().sc,0); // cout<<q.top().sc<<" "; q.pop(); }//cout<<endl; f[i]=(f[i]+query(1,0,n,max(0ll,i-2*y[i]),i,i%2))%M; // cout<<"!"<<i<<" "<<max(0ll,2*x[i]-i+1)<<" "<<i<<" "<<i%2<<" "<<query(1,0,n,max(0ll,i-2*y[i]),i,i%2)<<" "<<f[i]<<endl; // cout<<i<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].od<<" ";cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].ev<<" ";cout<<endl<<endl; update(1,0,n,i,f[i]); } // for(int i=1;i<=n;i++)cout<<f[i]<<endl; printf("%lld\n",f[n]); } return 0; }