# include <cstdlib>
# include <tuple>
# include <utility>
# include <cassert>
# include <vector>
# include <algorithm>
# include <cstdio>
# include <iostream>

namespace khin {
  using namespace std;
  namespace main {
    inline namespace source {}
    namespace d { void main(); }
  }
}

int main() { khin::main::d::main(); }

namespace khin::main::d {
  namespace test_case {
    constexpr uint mod(1'000'000'007);
    constexpr uint n_max(5'000);
    struct box { char c; uint b; uint f; bool vis; };
    uint n; box b[n_max + 1]; uint ans;
    void main(ushort const x) {
      cin >> n;
      for (uint i(1); i <= n; ++i) cin >> b[i].c;
      for (uint i(1); i <= n; ++i) cin >> b[i].b;
      [] {
        vector<uint> c(1, n);
        while (b[c.back()].vis = true, !b[b[c.back()].b].vis)
          c.push_back(b[c.back()].b);
        for (uint const x : c) b[x].vis = false;
        c.erase(c.begin(), find(c.begin(), c.end(), b[c.back()].b));
        b[*min_element(c.begin(), c.end())].vis = true;
      } ();
      for (uint const x : { 0, 1 }) for (uint const y : { 0, 1 }) {
        for (uint i(1); i <= n; ++i) switch (b[i].c) {
          case 'C': b[i].f = 1; break;
          case '.': b[i].f = 0; break;
          case '?': b[i].f = (mod + 1) / 2; break;
          default : assert(false);
        }
        uint r(1);
        for (uint i(1); i <= n; ++i) {
          if (b[i].vis) {
            uint &p(b[i].f), &q(b[b[i].b].f);
            r = 1ul * r * (x ? p : 1 - p + mod) % mod;
            r = 1ul * r * (y ? q : 1 - q + mod) % mod;
            p = x && y, q = x || y;
          } else {
            uint &p(b[i].f), &q(b[b[i].b].f);
            uint const x(1ul * p * q % mod);
            uint const y((p + q - 1ul * p * q % mod + mod) % mod);
            tie(p, q) = make_pair(x, y);
          }
        }
        ans = (ans + 1ul * r * b[n].f) % mod;
      }
      for (uint i(1); i <= n; ++i)
        ans = ans * (b[i].c == '?' ? 2 : 1) % mod;
      printf("Case #%hu: %u\n", x, ans);
      fill(b + 1, b + n + 1, box()), ans = 0;
    }
  }
  void main() {
    ushort t; cin >> t;
    for (ushort i(1); i <= t; ++i) test_case::main(i);
  }
}