{"raw_statement":[{"iden":"background","content":"翻译自 [ROIR 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。\n\n如果对于任意长度为 $2$ 的字符串 $u$，字符串 $s$ 中 $u$ 的出现次数与字符串 $t$ 中 $u$ 的出现次数相同，则两个字符串 $s$ 和 $t$ 称为等效字符串。因此，字符串 `aaaba`、`abaaa` 和 `baaab` 彼此等效（字符串 `aa` 出现两次，字符串 `ab` 出现一次，字符串 `ba` 出现一次，字符串 `bb` 不作为子串出现），而字符串 `cff` 和 `ccf` 则不等效。一个字符串和它本身是等效的。"},{"iden":"statement","content":"在这个问题中，你将会得到 $Q$ 个由字符 `a`、`b` 和 `c` 组成的字符串，对于每个字符串，需要计算与它等效的由字符 `a`、`b` 和 `c` 组成的非空字符串的数量。由于这个数量可能非常大，所以要求对 $10^9 + 7$ 取余。"},{"iden":"input","content":"第一行输入一个数 $G$，表示当前子任务的编号。在样例中 $G=0$，本题另设一个分值为 $0$ 的 Subtask 0 来存储样例数据。\n\n第二行输入一个整数 $q$。\n\n接下来 $q$ 行，每行一个字符串。"},{"iden":"output","content":"对于每个字符串输出一行一个整数表示答案，记得取模 $10^9+7$。"},{"iden":"note","content":"样例说明：\n\n- 字符串 `abaa` 等效于字符串 `abaa`、`aaba`、`baab`；\n- 字符串 `abca` 等效于字符串 `abca`、`bcab`、`cabc`；\n- 字符串 `ccbca` 等效于字符串 `ccbca` 和 `cbcca`；\n- 字符串 `bacc` 只等效于字符串 `bacc`。\n\n本题使用捆绑测试。\n\n$n_i$ 表示第 $i$ 个输入字符串的长度，$L$ 表示所有字符串的长度之和，$w$ 表示所有查询中最大（未取模）的答案。\n\n| 子任务编号 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $0$ | $0$ | 输入数据与样例相同 |\n| $1$ | $11$ | $s$ 中不含 `c` |\n| $2$ | $13$ | $s$ 中 `a` 与 `c` 不相邻 |\n| $3$ | $11$ | $n_i\\le13$ |\n| $4$ | $10$ | $L\\le40$ |\n| $5$ | $9$ | $L\\le60$ |\n| $6$ | $13$ | $L\\le10^5,w\\le100$ |\n| $7$ | $33$ | 无 |\n\n对于 $100\\%$ 数据，$1\\le q\\le10^5$，$L\\le10^6$。"}],"translated_statement":null,"sample_group":[["0\n4\nabaa\nabca\nccbca\nbacc","3\n3\n2\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}