#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7, inv2 = 500000004;
int n, b[5005], cut;
char s[5005];
struct dsu
{
    int fa[5005];
    void init()
    {
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }
    int find(int x) { return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
} t1, t2;
int f[5005];
inline int fan(int x) { return (1 - x + mod) % mod; }
void sol()
{
    cin >> n >> s + 1;
    t1.init();
    t2.init();
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        if (t1.find(i) != t1.find(b[i]))
        {
            t1.fa[t1.find(i)] = t1.find(b[i]);
        }
    }
    for (int i = n; i >= 1; i--)
    {
        if (t1.find(i) != t1.find(n))
            continue;
        if (t2.find(i) == t2.find(b[i]))
        {
            cut = i;
        }
        t2.fa[t2.find(i)] = t2.find(b[i]);
    }
    int p, ans = 0;
    for (int c1 = 0; c1 <= 1; c1++)
    {
        for (int c2 = 0; c2 <= 1; c2++)
        {
            for (int i = 1; i <= n; i++)
            {
                if (s[i] == 'C')
                    f[i] = 1;
                else if (s[i] == '?')
                    f[i] = inv2;
                else
                    f[i] = 0;
            }
            for (int i = 1; i <= n; i++)
            {
                if (i == cut)
                {
                    p = (c1 ? f[cut] : fan(f[cut])) * (c2 ? f[b[cut]] : fan(f[b[cut]])) % mod;
                    f[cut] = c1;
                    f[b[cut]] = c2;
                }
                int pi = f[i], pb = f[b[i]];
                f[i] = pi * pb % mod;
                f[b[i]] = (pi + pb * fan(pi) % mod) % mod;
            }
            ans = (ans + p * f[n] % mod) % mod;
        }
    }
    for (int i = 1; i <= n; i++)
        if (s[i] == '?')
            ans = ans * 2 % mod;
    cout << ans << '\n';
}
signed main()
{
    // freopen("experiment.in", "r", stdin);
    // freopen("experiment.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        cout<<"Case #" << i << ": ";
        sol();
    }
    return 0;
}