P10047 [CCPC 2023 Beijing City Contest] Do Not Disturb Pets.

Ene likes palindromes. Ene now has some words. She wants to choose some words and concatenate them end to end to form a palindrome string with length exactly $L$. Each word can be chosen multiple times, or not chosen at all. Ene wants to know the number of ways to do this. Ene considers two ways different if and only if the number of occurrences of each word is different, or their arrangement order is different. Note that multiple different ways may produce the same palindrome string. Since the answer may be very large, you need to output the answer modulo $1,000,000,007$.

The first line contains two positive integers $N, L$, representing the number of words and the required length of the palindrome string. It is guaranteed that $1\le N\le 333$, $1\le L\le 1000$. The next $N$ lines each contain a string $s_i$, representing a word. It is guaranteed that $1\le |s_i| \le L$, $\sum_{i=1}^N |s_i| \le 600$. The input words contain only lowercase letters and are pairwise distinct.

Output a non-negative integer, representing the number of ways to form a palindrome string modulo $1,000,000,007$.

**[Sample Explanation 1]** There are the following five ways: - `stack` `cats` - `evil` `olive` - `eel` `eve` `lee` - `lee` `eve` `eel` - `eve` `eve` `eve` **[Sample Explanation 2]** There are the following two ways: - `a` `a` - `aa` Translated by ChatGPT 5