Обыкновенная задача про строки
(Время: 2 сек. Память: 32 Мб Сложность: 78%)
Назовем две строки s и t эквивалентными, если для любой строки u длины 2, количество вхождений u в s совпадает с количеством вхождением u в t. Таким образом, строки «aaaba», «abaaa» и «baaab» попарно эквивалентны между собой (строка «aa» входит два раза, строка «ab» один раз, строка «ba» один раз, строка «bb» не входит как подстрока), а строки «abb» и «bba» – нет.
В этой задаче вам будут даны Q строк, состоящих из символов «a», «b» и «c», для каждой из которых надо будет посчитать количество эквивалентных им непустых строк, также состоящих из символов «a», «b» и «c». Так как это количество может быть очень большим, то надо вывести его остаток при делении на 109+7.
Входные данные
В первой строке входного файла INPUT.TXT дано число G – номер подзадачи, к которой относится текущий тест. Для теста из примера G = 0.
На второй строке дано число Q (1 ≤ Q ≤ 105), затем следуют Q строк, состоящих из символов «a», «b» и «c». Суммарная длина строк не превышает 106.
Выходные данные
В выходной файл OUTPUT.TXT требуется вывести Q целых чисел – для каждой строки необходимо вывести количество эквивалентных ей по модулю 109+7.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 0
4
abaa
abca
ccbca
bacc | 3 3 2 1 |
Пояснение к примеру
Строке «abaa» эквивалентны строки «abaa», «aaba» и «baab».
Строке «abca» эквивалентны строки «abca», «bcab» и «cabc».
Строке «ccbca» эквивалентны строки «ccbca» и «cbcca».
Строке «bacc» эквивалентна только строка «bacc».
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|