- Описание
- Отправленные решения
7. Обыкновенная задача про строки
Назовем две строки $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».
Ограничения
Ограничение времени
2 с
Ограничение памяти
512 МБ
Пример 1
0
4
abaa
abca
ccbca
bacc
3
3
2
1