- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define endl "\n"
- #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define ALL(x) x.begin(),x.end()
- #define SORT(x) sort(ALL(x))
- #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
- #define REP(a,b) FOR(a,0,b)
- #define mp make_pair
- #define pb push_back
- #define pll pair<ll,ll>
- #define pii pair<int,int>
- #define vl vector<ll>
- #define vi vector<int>
- #define f first
- #define s second
- ll ttt = 1, case_ = 0, n;
- ll const MOD = 1e9+7, MAXN = 8e5+5;
- vector<ll> facs(MAXN), inv_facs(MAXN);
- ll add_(ll a, ll b) {
- return (a + b) % MOD;
- }
- ll sub_(ll a, ll b) {
- return (a + MOD - b) % MOD;
- }
- ll mult_(ll a, ll b) {
- return (a*b) % MOD;
- }
- ll power(ll x,ll y,ll p)
- {
- ll res = 1;
- x = x % p;
- if (x == 0) return 0;
- while (y > 0)
- {
- if (y & 1)
- res = (res*x) % p;
- y = y>>1; // y = y/2
- x = (x*x) % p;
- }
- return res;
- }
- ll div_(ll a, ll b) {
- return mult_(a,power(b,MOD-2,MOD));
- }
- ll ncr(ll n, ll r){
- if (r > n || n < 0 || r < 0) return 0;
- return mult_(mult_(facs[n],inv_facs[r]),inv_facs[n-r]);
- }
- void get_facs() {
- facs[0] = 1;
- for (int i = 1; i < MAXN; i++) {
- facs[i] = mult_(facs[i-1],i);
- }
- inv_facs[MAXN-1] = power(facs[MAXN-1],MOD-2,MOD);
- for (int i = MAXN-2; i >= 0; i--) {
- inv_facs[i] = mult_(inv_facs[i+1],i+1);
- }
- }
- template <class myType>
- void print_arr(myType &arr, ll L, string sep){ REP(i,L) {
- cout << arr[i]; if (i < L-1) cout << sep;
- } cout << endl; return; }
- /*
- When we add an F, dp[i] = dp[i-1]
- When we add an O, dp[i] = dp[i-1] + index of previous X
- When we add an X, dp[i] = dp[i-1] + index of previous O
- What happens when we duplicate?
- XOOFXO|XOOFXO - we need to immediately compute the answer for each new index. How do we do that?
- Treat dp[prev] = 0 as a special case: just doubles to 0
- dp[7] = dp[6] + 6
- dp[8] = dp[6] + 6 + 7
- dp[9] = dp[6] + 6 + 7
- dp[10] = dp[6] + 6 + 7
- dp[11] = dp[6] + 6 + 7 + 9
- dp[12] = dp[6] + 6 + 7 + 9 + 11
- The total is LEN * prev + sum( F(j) ) where j is an index which is the last of its kind in the substring
- Suppose that O is the last O in a block of Os and Fs, and O is at index i.
- F(j) = j*(pos of next different index)
- We can't keep track of all these indices, it's not feasible.
- Instead need to find a way to calculate G(S + S) based on G(S).
- There are 3 types of substring:
- 1. Entirely within first half. Total G(S)
- 2. Entirely within second half. Total G(S)
- 3. Starts in first half, ends in second half.
- XOOFXO|XOOFXO
- Every one that starts in the first half and ends in the second half has a change in the middle if first_non_f != last_non_f
- How many times does each change get counted? A change has two key values [prev_idx, new_idx], and the number of substrings which incorporate that change is
- prev_idx * (LEN - new_idx + 1)
- When we duplicate, each change in the first half is counted by prev_idx*LEN additional times
- Each change in the second half is counted by LEN*(LEN - new_idx + 1) times
- And there may be a new change introduced which would be counted last_idx * (LEN - first_idx + 1) times
- And our new set of indices is equal to our old set plus LEN, so we have (i0, i2, ..., ix, i0 + LEN, ..., ix + LEN)
- Suppose we have a set of changes marked [l_dist, r_dist]
- The new set of changes is [l_dist, r_dist + LEN], [l_dist + LEN, r_dist], and a possible extra one in the middle
- sum ( l_dist*(r_dist + LEN) + (l_dist + LEN)*r_dist ) (plus the extra one maybe)
- = 2*l_dist*r_dist + LEN*(sum(l_dist) + sum(r_dist)) = 2*G(S) + LEN*sum(l_dist + r_dist) + one in the middle
- How does everything morph in transition?
- sum(l_dist) -> l_dist + num_changes*LEN + l_dist + possible extra
- sum(r_dist) -> r_dist + num_changes*LEN + r_dist + possible extra
- The 'possible extra' l_dist is equal to the index of the last non-F and the r_dist is equal to the first non-F + LEN
- If we add an F on the end, what happens? Each r_dist value increases by 1
- [l_dist, r_dist + 1] = l_dist*r_dist + l_
- L1*(R1 + 1), L2*(R1 + 2), etc
- If we add an O on the end, all the same things are true but we might be creating a new change as well
- */
- void solve() {
- case_++;
- cout << "Case #" << case_ << ": ";
- cin >> n;
- string S;
- cin >> S;
- ll curr = -1, prev_x = -1, first_x = -1, prev_o = -1, first_o = -1, LEN = 0, ans = 0, l_dist = 0, r_dist = 0, num_changes = 0;
- for(char c: S) {
- if (c == 'F') {
- LEN = add_(LEN, 1);
- ans = add_(ans, l_dist);
- r_dist = add_(r_dist,num_changes);
- }
- else if (c == 'O') {
- LEN = add_(LEN, 1);
- if (first_o == -1 && first_x == -1) first_o = LEN;
- prev_o = LEN;
- ans = add_(ans, l_dist);
- if (curr == 1) {
- l_dist = add_(l_dist, prev_x);
- num_changes = add_(num_changes,1);
- ans = add_(ans, prev_x);
- }
- r_dist = add_(r_dist, num_changes);
- curr = 0;
- }
- else if (c == 'X') {
- LEN = add_(LEN, 1);
- if (first_x == -1 && first_o == -1) first_x = LEN;
- prev_x = LEN;
- ans = add_(ans, l_dist);
- if (curr == 0) {
- l_dist = add_(l_dist, prev_o);
- num_changes = add_(num_changes,1);
- ans = add_(ans, prev_o);
- }
- r_dist = add_(r_dist, num_changes);
- curr = 1;
- }
- else {
- ll tmp = mult_(ans,2);
- tmp = add_(tmp, mult_(LEN,add_(l_dist,r_dist)));
- l_dist = add_(mult_(l_dist,2), mult_(num_changes,LEN));
- r_dist = add_(mult_(r_dist,2), mult_(num_changes,LEN));
- num_changes = mult_(num_changes,2);
- //cout << tmp << endl;
- if (first_x == -1 && first_o >= 0 && prev_x > prev_o) {
- // add a change
- num_changes = add_(num_changes,1);
- tmp = add_(tmp,mult_(prev_x, sub_(add_(LEN,1), first_o)));
- l_dist = add_(l_dist, prev_x);
- r_dist = add_(r_dist, sub_(add_(LEN,1), first_o));
- }
- else if (first_o == -1 && first_x >= 0 && prev_o > prev_x) {
- num_changes = add_(num_changes,1);
- tmp = add_(tmp,mult_(prev_o, sub_(add_(LEN,1), first_x)));
- //cout << prev_o << " " << LEN+1-first_x << endl;
- l_dist = add_(l_dist, prev_o);
- r_dist = add_(r_dist, sub_(add_(LEN,1), first_x));
- }
- prev_x = add_(prev_x, LEN);
- prev_o = add_(prev_o, LEN);
- LEN = mult_(LEN,2);
- ans = tmp;
- }
- //cout << LEN << ": " << l_dist << " " << r_dist << " " << ans << endl;
- //cout << LEN << ": " << ans << endl;
- }
- cout << ans << endl;
- return;
- }
- int main(){
- quick;
- freopen("C_in.txt", "r", stdin);
- freopen("C_out.txt", "w", stdout);
- cin >> ttt;
- while (ttt--) solve();
- return 0;
- }