#include<bits/stdc++.h> #define int long long using namespace std; const int N=5e5+7; const int mod=1e9+7; int n; string S; int PreR[N]; int PreB[N]; vector<int> Tran[N]; int Sum[N],f[N]; signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("dream.in","r",stdin); freopen("dream.out","w",stdout); #endif int T; cin>>T; while(T--){ cin>>n>>S;S=" "+S; int LR=0,LB=0; for(int i=1;i<=n;i++){ PreR[i]=LR,PreB[i]=LB; if(S[i]=='R')LR=i; if(S[i]=='B')LB=i; } for(int i=1;i<=n;i++)Tran[i].clear(),f[i]=0; for(int i=1;i<=n;i++){ if(S[i]=='X')Tran[i].push_back(i); if(S[i]=='B')for(int j=i;j<=min(n,i*2-PreB[i]-2);j++)Tran[j].push_back(i); }Sum[0]=f[0]=1; for(int i=1;i<=n;i++){ if(S[i]=='R'){Sum[i]=Sum[i-2];continue;} if(S[i]=='X')f[i]=f[i-1];//填 W int MaxHalfLen=i-PreR[i];//合法染色段的左半部分的最长长度 for(auto j:Tran[i]){ int HalfL=i-j+1; int HalfR=min(MaxHalfLen,(i-PreB[j])>>1); if(HalfL>HalfR)continue; int L=i-2*HalfR,R=i-2*HalfL; if(L>R)continue; (f[i]+=(Sum[R]-(L<2?0:Sum[L-2])+mod)%mod)%=mod; }Sum[i]=(i==1?f[i]:Sum[i-2]+f[i])%mod; }cout<<f[n]<<endl; }return 0; }