P4052 [JSOI2007] Text Generator

JSOI assigned team member ZYX a task to develop a computer program called "Text Generator." The users of this software are young children, and they are currently using the GW Text Generator v6. This software can randomly generate some text — it always generates a text with fixed length and completely random characters. That is, each character in the generated text is completely random. If a text contains at least one word known by the users, then we say the text is readable (we say a text $s$ contains a word $t$ if and only if $t$ is a substring of $s$). However, even under such a standard, the texts generated by the current GW Text Generator v6 are almost entirely unreadable. ZYX needs to determine, among all texts generated by GW Text Generator v6, how many are readable, in order to successfully obtain the v7 update. Can you help him? Output the answer modulo $10^4 + 7$.

The first line contains two integers, denoting the total number of words known by the users $n$ and the length of the generated text $m$. The next $n$ lines each contain a string $s_i$, representing a word known by the users.

Output a single integer: the answer modulo $10^4 + 7$.

Constraints and Conventions For all test points, it is guaranteed that: - $1 \leq n \leq 60$, $1 \leq m \leq 100$. - $1 \leq |s_i| \leq 100$, where $|s_i|$ denotes the length of string $s_i$. - Each $s_i$ contains only uppercase English letters. Translated by ChatGPT 5