Background

Translated from ROIR 2023 D2T4。

If for any string $u$ of length $2$, the number of occurrences of $u$ in string $s$ is the same as the number of occurrences of $u$ in string $t$, then the two strings $s$ and $t$ are called equivalent strings. Therefore, the strings aaaba, abaaa, and baaab are equivalent to each other (the substring aa appears twice, ab appears once, ba appears once, and bb does not appear as a substring), while cff and ccf are not equivalent. A string is equivalent to itself.

Problem Description

In this problem, you are given $Q$ strings consisting of the characters a, b, and c. For each string, you need to compute the number of non-empty strings consisting of the characters a, b, and c that are equivalent to it. Since this number can be very large, output it modulo $10^9 + 7$.

Input Format

The first line contains an integer $G$, which indicates the index of the current subtask. In the sample, $G=0$. This problem also provides an additional Subtask 0 with score $0$ to store the sample testdata.

The second line contains an integer $q$.

The next $q$ lines each contain a string.

Output Format

For each string, output one line with one integer representing the answer, modulo $10^9+7$.

0
4
abaa
abca
ccbca
bacc

3
3
2
1

Hint

Sample explanation:

• The string abaa is equivalent to abaa, aaba, baab；
• The string abca is equivalent to abca, bcab, cabc；
• The string ccbca is equivalent to ccbca and cbcca；
• The string bacc is only equivalent to bacc.

This problem uses bundled tests.

Let $n_i$ be the length of the $i$-th input string, $L$ be the sum of lengths of all strings, and $w$ be the maximum (not modulo) answer among all queries.

Constraints

For $100\%$ of the testdata, $1\le q\le10^5$ and $L\le10^6$.

Translated by ChatGPT 5