P10101 [ROIR 2023] 一个普通的字符串问题 (Day 2)

翻译自 [ROIR 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。 如果对于任意长度为 $2$ 的字符串 $u$，字符串 $s$ 中 $u$ 的出现次数与字符串 $t$ 中 $u$ 的出现次数相同，则两个字符串 $s$ 和 $t$ 称为等效字符串。因此，字符串 `aaaba`、`abaaa` 和 `baaab` 彼此等效（字符串 `aa` 出现两次，字符串 `ab` 出现一次，字符串 `ba` 出现一次，字符串 `bb` 不作为子串出现），而字符串 `cff` 和 `ccf` 则不等效。一个字符串和它本身是等效的。

在这个问题中，你将会得到 $Q$ 个由字符 `a`、`b` 和 `c` 组成的字符串，对于每个字符串，需要计算与它等效的由字符 `a`、`b` 和 `c` 组成的非空字符串的数量。由于这个数量可能非常大，所以要求对 $10^9 + 7$ 取余。

第一行输入一个数 $G$，表示当前子任务的编号。在样例中 $G=0$，本题另设一个分值为 $0$ 的 Subtask 0 来存储样例数据。 第二行输入一个整数 $q$。 接下来 $q$ 行，每行一个字符串。

对于每个字符串输出一行一个整数表示答案，记得取模 $10^9+7$。

样例说明： - 字符串 `abaa` 等效于字符串 `abaa`、`aaba`、`baab`； - 字符串 `abca` 等效于字符串 `abca`、`bcab`、`cabc`； - 字符串 `ccbca` 等效于字符串 `ccbca` 和 `cbcca`； - 字符串 `bacc` 只等效于字符串 `bacc`。 本题使用捆绑测试。 $n_i$ 表示第 $i$ 个输入字符串的长度，$L$ 表示所有字符串的长度之和，$w$ 表示所有查询中最大（未取模）的答案。 | 子任务编号 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 输入数据与样例相同 | | $1$ | $11$ | $s$ 中不含 `c` | | $2$ | $13$ | $s$ 中 `a` 与 `c` 不相邻 | | $3$ | $11$ | $n_i\le13$ | | $4$ | $10$ | $L\le40$ | | $5$ | $9$ | $L\le60$ | | $6$ | $13$ | $L\le10^5,w\le100$ | | $7$ | $33$ | 无 | 对于 $100\%$ 数据，$1\le q\le10^5$，$L\le10^6$。