Запретные слова манасчи


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Сказители «Манаса» верят, что некоторые сочетания звуков приносят несчастье. Ученики сочиняют напевы — строки длины L из первых σ строчных латинских букв. Напев можно исполнять, только если ни одно из k запретных слов не встречается в нём как подстрока (подряд идущие буквы).

Рисунок

Сколько существует напевов длины L, которые можно исполнять? Ответ выведите по модулю 10⁹ + 7.

Входные данные

В первой строке — три целых числа σ, k, L (1 ≤ σ ≤ 26, 1 ≤ k ≤ 100, 1 ≤ L ≤ 10¹⁸). В каждой из следующих k строк — непустое запретное слово из первых σ букв. Суммарная длина запретных слов не больше 100.

Выходные данные

Выведите количество напевов по модулю 10⁹ + 7.

Пример 1

Вход:

2 2 4
aa
bab

Выход:

4

Пояснение

Подходят 4 строки длины 4 из букв a и b: abba, abbb, bbba, bbbb. Например, abab не подходит — в ней есть bab, а baab — в ней есть aa.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов L ≤ 14 и σ ≤ 4.

Подсказка

Автомат Ахо — Корасик для запретных слов превращает задачу в подсчёт путей длины L в графе, а такие пути считаются возведением матрицы в степень.


Комментарии

Еще нет ни одного комментария.