Matcom Online Grader

El tabú es un juego en el que un jugador debe describir un concepto sin usar ninguna palabra de una lista. Si el equipo es capaz de adivinar el concepto ganan un punto. Si el jugador no puede describir el concepto o menciona una de las palabras de la lista entonces pierden el punto.

Fito está implementando un juego con una dinámica similar. Al inicio se crea una lista con $N$ palabras que se consideran tabú. Después se debe crear un texto que no contenga ninguna palabra de la lista. Para comprobar las ocurrencias se eliminan del texto los espacios y los signos de puntuación. Con este paso hacemos el juego un poco más difícil porque no permitimos que el fin de una palabra y el comienzo de la que le sigue en el texto formen una de las palabras prohibidas.

Ahora Fito quiere saber cuántos textos con $L$ letras no contienen ninguna de las palabras como substring. En este caso Fito quiere probar con tamaños muy grandes para el texto aunque después le sea imposible crear un texto de dicha longitud.

La primera línea de la entrada contiene dos enteros $N (1 \leq N \leq 10)$ y $L (1 \leq L \leq 10^9)$ que indican la cantidad de palabras prohibidas y la longitud de los textos buscados respectivamente. Le siguen las $N$ palabras en líneas distintas $(1 \leq |P_i | \leq 10)$. Las palabras y los textos que se deben formar están compuestos por letras minúsculas del alfabeto latino.

Se debe imprimir la cantidad de textos de $L$ letras que no contienen ninguna palabra como substring. Como dicho valor puede ser muy grande se debe imprimir el resto  de su división por $10^9+7$.