Рассмотрим $n$ исходных строк из строчных букв, причём ни одна исходная строка не является префиксом другой исходной строки. Выберем $k$ строк (каждую не более одного раза) и соединим их. Таким способом можно получить следующее количество составных строк:

$$n \times (n-1) \times (n-2) \times \ldots \times (n-k+1)$$

Отсортируем все составные строки, полученные таким способом, в алфавитном порядке. Вам дана проверяемая составная строка, которая гарантированно присутствует в этом списке. Найдите её позицию в упорядоченном по алфавиту списке всех составных строк по модулю $10^9 + 7$. Первая составная строка в списке имеет позицию $1$.

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

Каждый входной файл содержит один тестовый случай. Обратите внимание, что ваша программа может запускаться несколько раз на разных входных данных. Каждый тест начинается со строки с двумя целыми числами: сначала $n$, затем $k$ ($1 \le k \le n$), где $n$ — число исходных строк, а $k$ — число исходных строк, выбираемых для получения составной строки. Верхние границы $n$ и $k$ определяются ограничениями на строки, приведёнными в следующих абзацах.

Каждая из следующих $n$ строк содержит строку из одной или нескольких строчных букв a..z. Это $n$ исходных строк. Гарантируется, что ни одна из исходных строк не является префиксом другой исходной строки.

Наконец, последняя строка содержит ещё одну строку, состоящую только из строчных букв a..z. Это проверяемая составная строка, позицию которой в отсортированном списке нужно найти. Гарантируется, что она является конкатенацией $k$ различных исходных строк.

Сумма длин всех входных строк, включая проверяемую строку, не превышает $10^6$ букв.

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

Выведите одно целое число — позицию проверяемой составной строки в списке отсортированных составных строк. Выведите это число по модулю $10^9 + 7$.

Примеры

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

5 3
a
b
c
d
e
cad

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

26

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

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

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

12451