1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ALL(x) x.begin(),x.end()
  7. #define SORT(x) sort(ALL(x))
  8. #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
  9. #define REP(a,b) FOR(a,0,b)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define vl vector<ll>
  15. #define vi vector<int>
  16. #define f first
  17. #define s second
  18. ll ttt = 1, case_ = 0, n;
  19. ll const MOD = 1e9+7, MAXN = 8e5+5;
  20. vector<ll> facs(MAXN), inv_facs(MAXN);
  22. ll add_(ll a, ll b) {
  23. return (a + b) % MOD;
  24. }
  26. ll sub_(ll a, ll b) {
  27. return (a + MOD - b) % MOD;
  28. }
  30. ll mult_(ll a, ll b) {
  31. return (a*b) % MOD;
  32. }
  34. ll power(ll x,ll y,ll p)
  35. {
  36. ll res = 1;
  37. x = x % p;
  38. if (x == 0) return 0;
  39. while (y > 0)
  40. {
  41. if (y & 1)
  42. res = (res*x) % p;
  43. y = y>>1; // y = y/2
  44. x = (x*x) % p;
  45. }
  46. return res;
  47. }
  49. ll div_(ll a, ll b) {
  50. return mult_(a,power(b,MOD-2,MOD));
  51. }
  53. ll ncr(ll n, ll r){
  54. if (r > n || n < 0 || r < 0) return 0;
  55. return mult_(mult_(facs[n],inv_facs[r]),inv_facs[n-r]);
  56. }
  58. void get_facs() {
  59. facs[0] = 1;
  60. for (int i = 1; i < MAXN; i++) {
  61. facs[i] = mult_(facs[i-1],i);
  62. }
  63. inv_facs[MAXN-1] = power(facs[MAXN-1],MOD-2,MOD);
  64. for (int i = MAXN-2; i >= 0; i--) {
  65. inv_facs[i] = mult_(inv_facs[i+1],i+1);
  66. }
  67. }
  69. template <class myType>
  70. void print_arr(myType &arr, ll L, string sep){ REP(i,L) {
  71. cout << arr[i]; if (i < L-1) cout << sep;
  72. } cout << endl; return; }
  74. /*
  75. When we add an F, dp[i] = dp[i-1]
  76. When we add an O, dp[i] = dp[i-1] + index of previous X
  77. When we add an X, dp[i] = dp[i-1] + index of previous O
  78. What happens when we duplicate?
  80. XOOFXO|XOOFXO - we need to immediately compute the answer for each new index. How do we do that?
  82. Treat dp[prev] = 0 as a special case: just doubles to 0
  84. dp[7] = dp[6] + 6
  85. dp[8] = dp[6] + 6 + 7
  86. dp[9] = dp[6] + 6 + 7
  87. dp[10] = dp[6] + 6 + 7
  88. dp[11] = dp[6] + 6 + 7 + 9
  89. dp[12] = dp[6] + 6 + 7 + 9 + 11
  91. The total is LEN * prev + sum( F(j) ) where j is an index which is the last of its kind in the substring
  93. Suppose that O is the last O in a block of Os and Fs, and O is at index i.
  94. F(j) = j*(pos of next different index)
  96. We can't keep track of all these indices, it's not feasible.
  98. Instead need to find a way to calculate G(S + S) based on G(S).
  99. There are 3 types of substring:
  100. 1. Entirely within first half. Total G(S)
  101. 2. Entirely within second half. Total G(S)
  102. 3. Starts in first half, ends in second half.
  104. XOOFXO|XOOFXO
  106. 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
  108. 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
  109. prev_idx * (LEN - new_idx + 1)
  111. When we duplicate, each change in the first half is counted by prev_idx*LEN additional times
  112. Each change in the second half is counted by LEN*(LEN - new_idx + 1) times
  113. And there may be a new change introduced which would be counted last_idx * (LEN - first_idx + 1) times
  114. And our new set of indices is equal to our old set plus LEN, so we have (i0, i2, ..., ix, i0 + LEN, ..., ix + LEN)
  116. Suppose we have a set of changes marked [l_dist, r_dist]
  118. The new set of changes is [l_dist, r_dist + LEN], [l_dist + LEN, r_dist], and a possible extra one in the middle
  120. sum ( l_dist*(r_dist + LEN) + (l_dist + LEN)*r_dist ) (plus the extra one maybe)
  122. = 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
  124. How does everything morph in transition?
  126. sum(l_dist) -> l_dist + num_changes*LEN + l_dist + possible extra
  127. sum(r_dist) -> r_dist + num_changes*LEN + r_dist + possible extra
  129. 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
  131. If we add an F on the end, what happens? Each r_dist value increases by 1
  133. [l_dist, r_dist + 1] = l_dist*r_dist + l_
  135. L1*(R1 + 1), L2*(R1 + 2), etc
  137. If we add an O on the end, all the same things are true but we might be creating a new change as well
  138. */
  140. void solve() {
  141. case_++;
  142. cout << "Case #" << case_ << ": ";
  143. cin >> n;
  144. string S;
  145. cin >> S;
  146. 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;
  147. for(char c: S) {
  148. if (c == 'F') {
  149. LEN = add_(LEN, 1);
  150. ans = add_(ans, l_dist);
  151. r_dist = add_(r_dist,num_changes);
  152. }
  153. else if (c == 'O') {
  154. LEN = add_(LEN, 1);
  155. if (first_o == -1 && first_x == -1) first_o = LEN;
  156. prev_o = LEN;
  157. ans = add_(ans, l_dist);
  158. if (curr == 1) {
  159. l_dist = add_(l_dist, prev_x);
  160. num_changes = add_(num_changes,1);
  161. ans = add_(ans, prev_x);
  162. }
  163. r_dist = add_(r_dist, num_changes);
  164. curr = 0;
  165. }
  166. else if (c == 'X') {
  167. LEN = add_(LEN, 1);
  168. if (first_x == -1 && first_o == -1) first_x = LEN;
  169. prev_x = LEN;
  170. ans = add_(ans, l_dist);
  171. if (curr == 0) {
  172. l_dist = add_(l_dist, prev_o);
  173. num_changes = add_(num_changes,1);
  174. ans = add_(ans, prev_o);
  175. }
  176. r_dist = add_(r_dist, num_changes);
  177. curr = 1;
  178. }
  179. else {
  180. ll tmp = mult_(ans,2);
  181. tmp = add_(tmp, mult_(LEN,add_(l_dist,r_dist)));
  182. l_dist = add_(mult_(l_dist,2), mult_(num_changes,LEN));
  183. r_dist = add_(mult_(r_dist,2), mult_(num_changes,LEN));
  184. num_changes = mult_(num_changes,2);
  185. //cout << tmp << endl;
  186. if (first_x == -1 && first_o >= 0 && prev_x > prev_o) {
  187. // add a change
  188. num_changes = add_(num_changes,1);
  189. tmp = add_(tmp,mult_(prev_x, sub_(add_(LEN,1), first_o)));
  190. l_dist = add_(l_dist, prev_x);
  191. r_dist = add_(r_dist, sub_(add_(LEN,1), first_o));
  192. }
  193. else if (first_o == -1 && first_x >= 0 && prev_o > prev_x) {
  194. num_changes = add_(num_changes,1);
  195. tmp = add_(tmp,mult_(prev_o, sub_(add_(LEN,1), first_x)));
  196. //cout << prev_o << " " << LEN+1-first_x << endl;
  197. l_dist = add_(l_dist, prev_o);
  198. r_dist = add_(r_dist, sub_(add_(LEN,1), first_x));
  199. }
  200. prev_x = add_(prev_x, LEN);
  201. prev_o = add_(prev_o, LEN);
  202. LEN = mult_(LEN,2);
  203. ans = tmp;
  204. }
  205. //cout << LEN << ": " << l_dist << " " << r_dist << " " << ans << endl;
  206. //cout << LEN << ": " << ans << endl;
  207. }
  208. cout << ans << endl;
  209. return;
  210. }
  212. int main(){
  213. quick;
  214. freopen("C_in.txt", "r", stdin);
  215. freopen("C_out.txt", "w", stdout);
  216. cin >> ttt;
  217. while (ttt--) solve();
  218. return 0;
  219. }