Запретные слова манасчи
Сказители «Манаса» верят, что некоторые сочетания звуков приносят несчастье. Ученики сочиняют напевы — строки длины 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 в графе, а такие пути считаются возведением матрицы в степень.
Комментарии