Description

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

Input Format

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

第二行输入一个整数 $q$。

接下来 $q$ 行，每行一个字符串。

Output Format

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

0
4
abaa
abca
ccbca
bacc

3
3
2
1

Hint

样例说明：

• 字符串 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$。