Problem: weak_typing_ch2 (2021 round1)

**Note: This problem shares similarities with Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A1/) and [3](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A3/). The solution to any chapter may help with solving the others, so please consider reading all of them first.**

Timmy the toddler is training to be a top typist. His teacher has assigned some homework in the form of a list of \(T\) string exercises to be typed, consisting of only the uppercase letters "F", "O", and "X".

Timmy is eating a popsicle on a hot summer afternoon, but still hopes to complete his homework. He would like to hold the popsicle with one hand, and type with the other. Unfortunately, Timmy is still a growing boy, and each of his hands is a tad too small to reach all the way across the keyboard. He can only reach the letters "F" and "X" with his left hand, and the letters "F" and "O" with his right.

Consider a string \(W\) which Timmy must type. Timmy may start typing with any hand of his choice (with the other holding the popsicle). He must then switch hands as necessary to type out the \(|W|\) letters in order, ending on any hand of his choice.

Let \(F(W)\) be the minimum number of times Timmy must switch hands to type such a string \(W\).

Given an exercise string \(S\) of length \(N\), let \(G(S)\) be the sum of \(F(W)\) over all substrings \(W\) of \(S\). Note that there are \(N*(N+1)/2\) such substrings. Please help Timmy compute the value of \(G(S)\) modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 75\)
\(1 \le N \le 800{,}000\)

Each string consists only of the letters "F", "O", and "X".
The sum of \(N\) across all exercises is at most \(4{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of exercises that Timmy has been assigned. For each exercise, there is first a line containing the single integer \(N\), followed by a second line containing the string \(S\) of length \(N\).


# Output

For the \(i\)th exercise, output a line containing *"Case #i: "* followed by a single integer, \(G(S)\) modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

In the first exercise, the only substring of "O" is "O" itself. \(F(``O") = 0\), as if Timmy begins with his right hand, he can type "O" without needing to switch to his left hand. The answer is therefore \(0\) modulo \(1{,}000{,}000{,}007 = 0\).

In the second exercise, there are \(6\) substrings to consider: "X", "F", "O", "XF", "FO", and "XFO". \(F\) has a value of \(0\) when evaluated on any of the first 5 of these, while \(F(``XFO") = 1\), as if Timmy begins with his left hand, he can type all \(3\) letters in order with \(1\) hand switch (for example, by switching to his right hand after typing the first letter). The answer is therefore \((0 + 0 + 0 + 0 + 0 + 1)\) modulo \(1{,}000{,}000{,}007 = 1\).

In the third exercise, \(F\) has a value of \(0\) when evaluated on any of the \(15\) substrings of "FFOFF", as Timmy can type each of them using only his right hand.

In the fourth exercise, \(F\) has a value of \(0\) for \(29\) of the substrings of \(S\), a value of \(1\) for another \(16\) of them, and a value of \(2\) for the remaining \(10\) of them. The answer is therefore \((0 * 29 + 1 * 16 + 2 * 10)\) modulo \(1{,}000{,}000{,}007 = 36\).


Sample input:
5
1
O
3
XFO
5
FFOFF
10
FXXFXFOOXF
13
XFOFXFOFXFOFX


Sample output:
Case #1: 0
Case #2: 1
Case #3: 0
Case #4: 36
Case #5: 146


Solution: As in Chapter 1, we should begin by observing that hand switches are required whenever, once "F"s are ignored, an "X" is followed by an "O" or vice versa.

We can iterate through \(S\) and identify all such pairs of letters (either an "X" followed by an "O", with only "F"s in between, or vice versa). For each such pair, if it involves letters at indices \(a\) and \(b\) in \(S\) (such that \(a \lt b\)), then it effectively contributes an addition of \(1\) to the value of \(F\) for each substring of \(S\) which includes the entire substring \(S_{a..b}\) (as each such substring would have a hand switch in between typing the pair's letters). There are \(a * (|S| - b + 1)\) such substrings, meaning that such a pair contributes an addition of \(a * (|S| - b + 1)\) to \(G(S)\). Therefore, we can add all of these products up in a total of \(O(N)\) time to arrive at the final value of \(G(S)\).

[See David Harmeyer's solution video here](https://youtu.be/O1giTvqaxzM).


Code: #include <iostream>
using namespace std;

const int MOD = 1000000007;

int N;
string S;

int solve() {
  cin >> N >> S;
  int p = -1, ans = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == 'F') {
      continue;
    }
    if (p >= 0 && S[i] != S[p]) {
      ans = (ans + (long long)(p + 1)*(N - i)) % MOD;
    }
    p = i;
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}