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

Назовем две строки $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 \le q \le 10^5$), затем следуют $q$ строк, состоящих из символов «a», «b» и «c». Суммарная длина строк не превышает $10^6$.

Требуется вывести $q$ целых чисел — для каждой строки необходимо вывести количество эквивалентных ей по модулю $10^9 + 7$.

Строке «abaa» эквивалентны строки «abaa», «aaba», «baab»;

Строке «abca» эквивалентны строки «abca», «bcab», «cabc»;

Строке «ccbca» эквивалентны строки «ccbca» и «cbcca»;

Строке «bacc» эквивалентна только строка «bacc».