Ene likes palindromes.

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

Ene wants to know the number of such sequences. Two sequences are considered different if the number of occurrences of each word is different or if their order is different. Note that different sequences may result in the same palindrome string. Since the answer can be very large, you need to output the answer modulo $1,000,000,007$.

Input

The first line contains two positive integers $N$ and $L$, representing the number of words and the required length of the palindrome, 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 consist only of lowercase English letters and are distinct.

Output

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

Examples

Input 1

7 9
cats
eel
eve
evil
lee
olive
stack

Output 1

5

Note 1

There are five possible sequences:

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

Input 2

2 2
a
aa

Output 2

2

Note 2

There are two possible sequences:

• a a
• aa

Input 3

6 12
aa
aab
no
on
pets
step

Output 3

43