Considera $n$ cadenas iniciales de letras minúsculas, donde ninguna cadena inicial es prefijo de otra cadena inicial. Ahora, considera elegir $k$ de las cadenas (ninguna más de una vez) y concatenarlas. Puedes formar esta cantidad de cadenas compuestas:

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

Considera ordenar alfabéticamente todas las cadenas compuestas que puedes obtener mediante este proceso. Se te da una cadena compuesta de prueba, que se garantiza que pertenece a esta lista. Encuentra la posición de esta cadena de prueba en la lista ordenada alfabéticamente de todas las cadenas compuestas, módulo $10^9+7$. La primera cadena compuesta de la lista está en la posición $1$.

Entrada

Cada entrada consiste en un único caso de prueba. Ten en cuenta que tu programa puede ejecutarse varias veces con distintas entradas. Cada caso de prueba comienza con una línea con dos enteros, primero $n$ y después $k$ ($1\le k\le n$), donde $n$ es el número de cadenas iniciales y $k$ es el número de cadenas iniciales que eliges para formar las cadenas compuestas. Los límites superiores de $n$ y $k$ están determinados por las restricciones sobre las cadenas de los párrafos siguientes.

Cada una de las siguientes $n$ líneas contiene una cadena formada por una o más letras minúsculas de a a z. Estas son las $n$ cadenas iniciales. Se garantiza que ninguna de las cadenas iniciales es prefijo de otra cadena inicial.

Por último, la última línea contiene otra cadena, formada únicamente por letras minúsculas de a a z. Esta es la cadena compuesta de prueba, cuya posición en la lista ordenada debes encontrar. Se garantiza que esta cadena de prueba es la concatenación de $k$ cadenas iniciales distintas.

La suma de las longitudes de todas las cadenas de entrada, incluida la cadena de prueba, no excede de $10^6$ letras.

Salida

Imprime un único entero: la posición de la cadena compuesta de prueba en la lista ordenada de cadenas compuestas. Imprime este número módulo $10^9+7$.

Ejemplos

Entrada 1

5 3
a
b
c
d
e
cad

Salida 1

26

Entrada 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

Salida 2

12451