Автодополнение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тор все-таки решился на покупку мобильного телефона, чтобы связываться со Мстителями было проще. В процессе написания смс-сообщений Тор не мог не заметить интересную и довольно полезную функцию — автодополнение. Эта функция по написанному непустому началу слова предлагает на выбор три самых популярных слова из своего словаря с таким же началом, чтобы для ускорения написания сообщения пользователь мог согласиться на одно из них, а не дописывать слово полностью (если таких слов меньше трех, предлагаются все возможные слова). Таким образом, пользователь при наборе сообщения может делать три действия — написать новую букву, удалить букву из конца написанного текста и согласиться на один из не более трех вариантов автодополнения.

Тони Старк любезно согласился взломать телефон Тора, чтобы узнать все слова из словаря, который использует функция автодополнения. Таких слов оказалось ровно n штук, а также оказалось, что автодополнение предлагает 3 самых первых слова из списка, то есть чем раньше слово находится в списке, тем популярнее оно считается. Тони также подметил, что система автодополнения устроена так, что если пользователь набрал слово s, и оно есть в словаре, то система не будет его предлагать.

Тор так заинтересовался автодополнением, что захотел узнать все способы набора своего сообщения s с помощью него. Понятно, что таких способов бесконечно много, поэтому Тор хочет найти все способы набора сообщения, используя не более k действий. Тор действует довольно логично и не собирается набирать новую букву так, что получившийся текст не будет являться префиксом желаемого сообщения s (однако он может согласиться на автодополнение, которое не будет являться префиксом s). Также после того, как сообщение s набрано, Тор может продолжить набор сообщения, если на текущий момент он сделал меньше k действий (а может и не продолжать и остановиться).

Для начала Тор решил ограничиться сообщениями, состоящими только из одного слова и находить не варианты набора сообщения, а только их количество по модулю 109 + 7. Помогите ему с этой задачей — по данному слову s, состоящему из строчных латинских букв, и числу k найдите количество способов написать слово s не более чем за k действий.

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

В первой строке содержится число n — количество слов из словаря (1 ≤ n ≤ 100).

В следующих n строках содержатся слова wi из словаря (1 ≤ |wi| ≤ 100). Гарантируется, что каждое слово из словаря состоит только из строчных латинских букв, а также что суммарная длина слов из словаря не превышает 103.

В n + 2 строке содержится строка s — слово, состоящее только из строчных латинских букв, которое хочет набрать Тор (1 ≤ |s| ≤ 100).

В последней строке содержится число k — максимальное количество действий (набор одного символа, удаление одного символа из конца текущего текста или соглашение на один из варинтов автодополнения), которое можно сделать (1 ≤ k ≤ 103).

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

В единственной строке выведите количество способов набрать слово s по модулю 109 + 7.

Примеры

Входные данные
4
abacaba
ababb
abcabac
babacb
abacb
6
Выходные данные
3
Входные данные
1
exactword
exactword
4
Выходные данные
7

Примечание

В первом примере возможны следующие три варианта написания слова «abacb»: