P10101 [ROIR 2023] An Ordinary String Problem (Day 2)

Translated from [ROIR 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。 If for any string $u$ of length $2$, the number of occurrences of $u$ in string $s$ is the same as the number of occurrences of $u$ in string $t$, then the two strings $s$ and $t$ are called equivalent strings. Therefore, the strings `aaaba`, `abaaa`, and `baaab` are equivalent to each other (the substring `aa` appears twice, `ab` appears once, `ba` appears once, and `bb` does not appear as a substring), while `cff` and `ccf` are not equivalent. A string is equivalent to itself.

In this problem, you are given $Q$ strings consisting of the characters `a`, `b`, and `c`. For each string, you need to compute the number of non-empty strings consisting of the characters `a`, `b`, and `c` that are equivalent to it. Since this number can be very large, output it modulo $10^9 + 7$.

The first line contains an integer $G$, which indicates the index of the current subtask. In the sample, $G=0$. This problem also provides an additional Subtask 0 with score $0$ to store the sample testdata. The second line contains an integer $q$. The next $q$ lines each contain a string.

For each string, output one line with one integer representing the answer, modulo $10^9+7$.

Sample explanation: - The string `abaa` is equivalent to `abaa`, `aaba`, `baab`； - The string `abca` is equivalent to `abca`, `bcab`, `cabc`； - The string `ccbca` is equivalent to `ccbca` and `cbcca`； - The string `bacc` is only equivalent to `bacc`. This problem uses bundled tests. Let $n_i$ be the length of the $i$-th input string, $L$ be the sum of lengths of all strings, and $w$ be the maximum (not modulo) answer among all queries. ## Constraints | Subtask ID | Score | Special Property | | :----------: | :----------: | :----------: | | $0$ | $0$ | The input testdata is the same as the sample | | $1$ | $11$ | $s$ contains no `c` | | $2$ | $13$ | `a` and `c` are not adjacent in $s$ | | $3$ | $11$ | $n_i\le13$ | | $4$ | $10$ | $L\le40$ | | $5$ | $9$ | $L\le60$ | | $6$ | $13$ | $L\le10^5,w\le100$ | | $7$ | $33$ | None | For $100\%$ of the testdata, $1\le q\le10^5$ and $L\le10^6$. Translated by ChatGPT 5