Назовем две строки $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$.

Подзадачи