题目描述

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

例如，字符串 aaaba、abaaa 和 baaab 两两等价：

• aa 出现 $2$ 次；
• ab 出现 $1$ 次；
• ba 出现 $1$ 次；
• bb 出现 $0$ 次。

而字符串 abb 和 bba 不等价。

现在给定 $Q$ 个只由字符 a、b、c 组成的字符串。对每个字符串，求与它等价的非空字符串数量，要求这些字符串也只由 a、b、c 组成。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

输入格式

第一行包含一个整数 $G$，表示当前测试所属的子任务编号。样例中 $G=0$。

第二行包含一个整数 $q$（$1\le q\le 10^5$）。接下来给出 $q$ 个字符串，每个字符串仅由 a、b、c 组成。

所有字符串的总长度不超过 $10^6$。

输出格式

输出 $q$ 个整数，每个整数对应一个输入字符串的答案。通常每行输出一个答案。

子任务

设 $n_i$ 为第 $i$ 个字符串的长度，$L$ 为所有输入字符串长度之和，$w$ 为所有询问中未取模的最大答案。

样例

0
4
abaa
abca
ccbca
bacc

3
3
2
1

样例解释

• 与 abaa 等价的字符串有：abaa、aaba、baab；
• 与 abca 等价的字符串有：abca、bcab、cabc；
• 与 ccbca 等价的字符串有：ccbca、cbcca；
• 与 bacc 等价的字符串只有：bacc。