시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB32266.667%

문제

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

서브태스크

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

번호배점제한
111

строка $s$ не содержит символов «c»

213

символы «a» и «c» в строке $s$ не встречаются рядом

311

$n_i \le 13$

410

$L \le 40$

59

$L \le 60$

613

$w \le 100$; $L \le 10^5$

733

нет

예제 입력 1

0
4
abaa
abca
ccbca
bacc

예제 출력 1

3
3
2
1

힌트

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

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

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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.