Автодополнение

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

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

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

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

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

В следующих $n$ строках содержатся слова $w\_i$ из словаря ($1 \le |w\_i| \le 100$). Гарантируется, что каждое слово из словаря состоит только из строчных латинских букв, а также что суммарная длина слов из словаря не превышает $10^3$.

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

В последней строке содержится число $k$ --- максимальное количество действий (набор одного символа, удаление одного символа из конца текущего текста или соглашение на один из варинтов автодополнения), которое можно сделать ($1 \le k \le 10^3$).

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

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

• $6$ действий: набрать букву <<a>> $\rightarrow$ согласиться на автодополнение <<abacaba>> $\rightarrow$ удалить $3$ раза последнюю букву $\rightarrow$ набрать букву <<b>>;
• $6$ действий: набрать букву <<a>> $\rightarrow$ согласиться на автодополнение <<ababb>> $\rightarrow$ удалить $2$ раза последнюю букву $\rightarrow$ набрать букву <<c>> $\rightarrow$ набрать букву <<b>>;
• $5$ действий: набрать слово по одной букве.