题目描述

译自 ROI Regional 2023 Day2 T4. Обыкновенная задача про строки

我们称两个字符串 $s$ 和 $t$ 是等价的，如果对于任意长度为 $2$ 的字符串 $u$，$u$ 在 $s$ 中出现的次数与在 $t$ 中出现的次数相同。

例如，字符串 aaaba、abaaa 和 baaab 彼此等价（aa 出现两次，ab 出现一次，ba 出现一次，bb 不出现），而字符串 abb 和 bba 则不等价。

在这个问题中，给定 $Q$ 个由字符 a、b 和 c 组成的字符串，对于每个字符串，需要计算有多少个与其等价的非空字符串，这些字符串也由 a、b 和 c 组成。由于这个数量可能非常大，需要输出其对 $10^{9}+7$ 取模的结果。

输入格式

第一行输入一个整数 $G$，表示当前测试点所属的子任务编号。对于样例，$G=0$。

第二行输入一个整数 $q$ $(1 \leq q \leq 10^5)$，接下来是 $q$ 行，每行是一个由字符 a、b 和 c 组成的字符串。这些字符串的总长度不超过 $10^6$。

输出格式

输出 $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。

数据范围与提示

详细子任务附加限制及分值如下表所示。