581. Обыкновенная задача про строки

Назовем две строки $s$ и $t$ эквивалентными, если для любой строки $u$ длины 2, количество вхождений $u$ в $s$ совпадает с количеством вхождением $u$ в $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$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. За $n_i$ обозначена длина $i$-й строки во входных данных, за $L$ обозначена сумма длин строк, за $w$ $-$ максимальный ответ (не взятый по модулю) среди всех запросов.

Пояснение к примеру:

• Строке «abaa» эквивалентны строки «abaa», «aaba», «baab»;
• Строке «abca» эквивалентны строки «abca», «bcab», «cabc»;
• Строке «ccbca» эквивалентны строки «ccbca» и «cbcca»;
• Строке «bacc» эквивалентна только строка «bacc».