题目背景

翻译自 ROIR 2023 D2T4。

如果对于任意长度为 $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$。

0
4
abaa
abca
ccbca
bacc

3
3
2
1

提示

样例说明：

• 字符串 abaa 等效于字符串 abaa、aaba、baab；
• 字符串 abca 等效于字符串 abca、bcab、cabc；
• 字符串 ccbca 等效于字符串 ccbca 和 cbcca；
• 字符串 bacc 只等效于字符串 bacc。

本题使用捆绑测试。

$n_i$ 表示第 $i$ 个输入字符串的长度，$L$ 表示所有字符串的长度之和，$w$ 表示所有查询中最大（未取模）的答案。

对于 $100\%$ 数据，$1\le q\le10^5$，$L\le10^6$。