Розглянемо $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