#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;

const long long MOD = 1e9 + 7;

long long gNaive(const string &s) {
    vector<pair<int, int>> pos;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'X')
            pos.push_back({ 1, i });
        if (s[i] == 'O')
            pos.push_back({ 2, i });
    }

    long long res = 0;

    for (int i = 1; i < pos.size(); i++) {
        if (pos[i - 1].first == pos[i].first)
            continue;

        long long l = pos[i - 1].second + 1;
        long long r = s.size() - pos[i].second;

        res = (res + l * r % MOD) % MOD;
    }

    return res;
}

long long g(const string &s) {
    long long len = 0;
    long long sumL = 0;
    long long sumR = 0;
    long long sumLR = 0;

    long long firstO = -1;
    long long firstX = -1;
    long long lastO = -1;
    long long lastX = -1;
    long long pairCount = 0;

    char firstChar = '?';
    char lastChar = '?';

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'F') {

            len = (len + 1) % MOD;
            sumR = (sumR + pairCount) % MOD;
            sumLR = (sumLR + sumL) % MOD;

        } else if (s[i] == 'O') {

            len = (len + 1) % MOD;
            sumR = (sumR + pairCount) % MOD;
            sumLR = (sumLR + sumL) % MOD;

            if (lastChar == 'X') {
                long long l = (lastX + 1) % MOD;
                long long r = 1 % MOD;

                sumLR = (sumLR + l * r % MOD) % MOD;
                sumL = (sumL + l) % MOD;
                sumR = (sumR + r) % MOD;
                pairCount = (pairCount + 1) % MOD;
            }

            if (firstChar == '?') {
                firstO = (len - 1 + MOD) % MOD;
                firstChar = 'O';
            }

            lastO = (len - 1 + MOD) % MOD;
            lastChar = 'O';

        } else if (s[i] == 'X') {

            len = (len + 1) % MOD;
            sumR = (sumR + pairCount) % MOD;
            sumLR = (sumLR + sumL) % MOD;

            if (lastChar == 'O') {
                long long l = (lastO + 1) % MOD;
                long long r = 1 % MOD;

                sumLR = (sumLR + l * r % MOD) % MOD;
                sumL = (sumL + l) % MOD;
                sumR = (sumR + r) % MOD;
                pairCount = (pairCount + 1) % MOD;
            }

            if (firstChar == '?') {
                firstX = (len - 1 + MOD) % MOD;
                firstChar = 'X';
            }

            lastX = (len - 1 + MOD) % MOD;
            lastChar = 'X';

        } else {

            sumLR = (sumLR * 2) % MOD;
            sumLR = (sumLR + len * sumL % MOD) % MOD;
            sumLR = (sumLR + len * sumR % MOD) % MOD;

            sumL = (sumL * 2) % MOD;
            sumL = (sumL + pairCount * len % MOD) % MOD;

            sumR = (sumR * 2) % MOD;
            sumR = (sumR + pairCount * len % MOD) % MOD;

            pairCount = (pairCount * 2) % MOD;

            if (firstChar == 'X' && lastChar == 'O') {
                long long l = (lastO + 1) % MOD;
                long long r = (len - firstX) % MOD;

                sumLR = (sumLR + l * r % MOD) % MOD;
                sumL = (sumL + l) % MOD;
                sumR = (sumR + r) % MOD;
                pairCount = (pairCount + 1) % MOD;
            }
            if (firstChar == 'O' && lastChar == 'X') {
                long long l = (lastX + 1) % MOD;
                long long r = (len - firstO) % MOD;

                sumLR = (sumLR + l * r % MOD) % MOD;
                sumL = (sumL + l) % MOD;
                sumR = (sumR + r) % MOD;
                pairCount = (pairCount + 1) % MOD;
            }

            if (lastO != -1)
                lastO = (lastO + len) % MOD;
            if (lastX != -1)
                lastX = (lastX + len) % MOD;
            len = (len * 2) % MOD;

        }
    }

    return sumLR;
}

string generateString(int size, int n) {
    string letters = ".FOX";
    string res;
    for (int i = 0; i < size; i++) {
        res += letters[n % 4];
        n /= 4;
    }
    return res;
}

string expandString(string &s) {
    string res;
    for (char c : s) {
        if (c == '.')
            res += res;
        else
            res += c;
    }
    return res;
}

void testG() {
    for (int size = 0, limit = 4; size <= 8; size++, limit *= 4) {
        for (int n = 1; n < limit; n++) {
            string s = generateString(size, n);
            if (s[0] == '.')
                continue;
            string es = expandString(s);

            long long res = g(s);
            long long resNaive = gNaive(es);

            if (res != resNaive) {
                cout << s << "\n";
                cout << es << "\n";
                cout << res << "\n";
                cout << resNaive << "\n";
                return;
            }
        }
    }

    cerr << "Max test:";
    for (int i = 0; i < 10; i++) {
        string s = generateString(4e6, rand() * rand());
        long long res = g(s);
        cerr << res << "\n";
    }
}

void solve(int test) {
    int n;
    string s;
    cin >> n >> s;

    cout << "Case #" << test << ": " << g(s) << "\n";
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    //testG();

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int test = 1; test <= n; test++)
        solve(test);
}