#include<bits/stdc++.h>
#define ll long long
#define il inline
#define vd void
#define bl bool
#define fr(x) freopen(#x".in","s",stdin);freopen(#x".out","w",stdout)
using namespace std;
const ll N=5e3+2,P=1e9+7;
struct zjy{char c;ll b,f;bl bz;}a[N];
il ll R()
{
    ll n=0,f=1;
    char c;
    for(c=getchar();c!='-'&&(c<'0'||c>'9');c=getchar());
    if(c=='-') f=-1,c=getchar();
    for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-'0';
    return n*f;
}
il vd W(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) W(x/10);
    putchar(x%10+'0');
}
signed main()
{
    ll n,i,ans,T,mn,z,s,tt;
    for(T=R(),tt=1;tt<=T;++tt)
    {
        for(n=R(),i=1;i<=n;++i) scanf("%c",&a[i].c);
        for(i=1;i<=n;++i) a[i].b=R();
        vector<ll> c(1,n);
        while(a[c.back()].bz=1,!a[a[c.back()].b].bz) c.push_back(a[c.back()].b);
        for(ll x:c) a[x].bz=0;
        c.erase(c.begin(),find(c.begin(),c.end(),a[c.back()].b));
        mn=N;
        for(ll x:c) mn=min(mn,x);
        a[mn].bz=1;
        for(ll x:{0,1})
        {
            for(ll y:{0,1})
            {
                for(i=1;i<=n;++i) a[i].f=a[i].c=='?'?P+1>>1:a[i].c=='C';
                for(s=i=1;i<=n;++i)
                {
                    ll &p=a[i].f,&q=a[a[i].b].f;
                    if(a[i].bz)
                    {
                        s=s*(x?p:1-p+P)%P*(y?q:1-q+P)%P;
                        p=x&&y,q=x||y;
                    }
                    else z=p,p=p*q%P,q=(z+q-z*q%P+P)%P;
                }
                ans=(ans+s*a[n].f)%P;
            }
        }
        for(i=1;i<=n;++i) ans=ans*(a[i].c=='?'?2:1)%P;
        cout<<"Case #"<<tt<<": ";
        W(ans);
        putchar('\n');
        memset(a,0,sizeof(a));
        ans=0;
    }
}