Разбиение слова


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

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

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

Разбиение слова

У Айгерим есть слово s и словарь из d различных слов. Сколькими способами можно записать s как последовательность подряд идущих слов словаря (слова можно использовать повторно)?

Ввод. В первой строке s (1 ≤ |s| ≤ 2000, строчные латинские буквы). Во второй d (1 ≤ d ≤ 50), далее d строк со словами длиной от 1 до 10.

Вывод. Число способов по модулю 10^9 + 7.

Пример

Ввод:

aabaab
3
a
aab
ab

Вывод:

4

Комментарии

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