Problem Description

Ene loves palindromes.

Ene has some words. She wants to select several words and concatenate them to form a palindrome string of exactly length $L$. Each word can be chosen multiple times or not at all.

Ene wants to know the number of ways to do this. Ene considers two schemes different if and only if the number of occurrences of each word is different or their arrangement order is different. Note that multiple different schemes might result in the same palindrome string. Since the answer might be very large, you need to take the modulo of $1,000,000,007$.

Input Format

The first line of input contains two positive integers $N, L$, representing the number of words and the length of the required palindrome string, respectively. It is guaranteed that $1 \le N \le 333$ and $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$ and $\sum_{i=1}^N |s_i| \le 600$; the input words only contain lowercase characters and are distinct.

Output Format

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

Sample Input and Output

Sample Input #1

7 9
cats
eel
eve
evil
lee
olive
stack

Sample Output #1

5

Sample Input #2

2 2
a
aa

Sample Output #2

2

Sample Input #3

6 12
aa
aab
no
on
pets
step

Sample Output #3

43

Notes

[Sample Explanation 1]

There are five ways:

• stack cats
• evil olive
• eel eve lee
• lee eve eel
• eve eve eve

[Sample Explanation 2]

There are two ways:

• a a
• aa

见题面 Input 部分

见题面 Output 部分