I - Recordando nombres II

Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)

Extenuados de tanto trabajar (o jugar), BitZero y BitOne han decidido regresar a casa. Resulta ser que mientras estaban ausentes, un escuadrón secreto de BitSecurity llamado Byte registró sus pertenencias en busca de algún resultado interesante, pero el conocimiento es invisible a los ojos de los ignorantes, por lo que no encontraron nada. Como algunos de los integrantes de Byte no estaban activos, el registro no fue realizado cuidadosamente y se estropearon algunos de los trabajos de BitZero y BitOne. Uno de ellos, en particular, era muy importante y consistía en una lista de $N$ palabras que cumplía ciertas propiedades. Lamentablemente la lista se desordenó, pero BitZero y BitOne tienen buena memoria. BitOne recuerda que había algunas palabras que eran prefijo de otras y BitZero recuerda que esto se cumplía consecutivamente para las primeras $K$ palabras de la lista, o sea, la primera palabra era prefijo de la segunda, la segunda de la tercera, y así sucesivamente hasta llegar a la $(K-1)$ésima palabra, que era prefijo de la $K$ésima. Del resto de las palabras en la lista no recuerdan ninguna propiedad. La tarea es ahora reconstruir la lista, pero pueden haber múltiple listas que cumplan con las condiciones que recuerdan.

Input

1ra línea : dos enteros $N$ y $K$ representando la cantidad de palabras en la lista y el número que recuerda BitZero respectivamente.
N siguientes líneas : una palabra de la lista de BitOne y BitZero.

Todas las palabras serán diferentes.
* Para el subproblema I se cumple que $1 \le N \le 500$, $1 \le K \le \min(50, N)$, la suma de las longitudes de las $N$ palabras es a lo sumo 100000 $(10^5)$.
* Para el subproblema II se cumple que $1 \le N \le 200000$, $1 \le K \le \min(50, N)$, la suma de las longitudes de las $N$ palabras es a lo sumo 1000000 $(10^6)$ .

Output

1ra línea : la cantidad de listas que cumplen con los recuerdos de BitZero y BitOne. Como la respuesta puede ser muy grande, sólo es necesario darla módulo 1000000007 $(10^9+7)$.

Sample test(s)

Input
3 2 a ab abc
Output
3
Input
3 1 bmp jpg png
Output
6
Input
13 2 cef b cehi ceg bde cd bdfg bc ceh c bd d bdf
Output
598752000