#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e3+5,P=1e9+7;

int n;
int fa[N],p[N];
char s[N];
int Fa[N][2];

int getfa(int x,int y)
{
    while(x!=Fa[x][y])
        x=Fa[x][y]=Fa[Fa[x][y]][y];
    return x;
}

int get(int x)
{
    return (1-x+P)%P;
}

void solve()
{
	scanf("%lld%s",&n,s+1);
	for(int i=1;i<=n;i++)
		scanf("%lld",&fa[i]);
    for(int i=1;i<=n;i++)
        Fa[i][0]=Fa[i][1]=i;
    for(int i=1;i<=n;i++){
		int x=getfa(i,0),y=getfa(fa[i],0);
		if(x!=y)
			Fa[y][0]=x;
	}
	int Ring;
	for(int i=n;i>=1;i--){
		int x=getfa(i,0),y=getfa(n,0);
		if(x==y){
			x=getfa(i,1),y=getfa(fa[i],1);
			if(x!=y)
				Fa[y][1]=x;
            else
                Ring=i;
		}
	}
	int ans=0;
	for(int l=0;l<=1;l++){
		for(int r=0;r<=1;r++){
			for(int i=1;i<=n;i++){
				if(s[i]=='C')
					p[i]=1;
				else if(s[i]=='.')
					p[i]=0;
				else
					p[i]=(1+P)/2;
			}
			int ring;
			for(int i=1;i<=n;i++){
				if(i==Ring){
					ring=(l?p[i]:get(p[i]))*(r?p[fa[i]]:get(p[fa[i]]))%P;
					p[i]=l,p[fa[i]]=r;
				}
				int x=p[i],y=p[fa[i]];
				p[i]=x*y%P;
				p[fa[i]]=(x+y*get(x)%P)%P;
			}
			(ans+=ring*p[n]%P)%=P;
		}
	}
    ans=(ans+P)%P;
	for(int i=1;i<=n;i++)
		if(s[i]=='?')
			ans=ans*2%P;
	printf("%lld\n",(ans+P)%P);
}
// #define IO IO
signed main()
{
    #ifdef IO
    freopen("experiment.in", "r", stdin);
    freopen("experiment.out", "w", stdout);
    #endif
	int T;
	scanf("%lld",&T);
    for(int i=1;i<=T;i++){
        cout<<"Case #"<<i<<": ";
		solve();
    }
	return 0;
}