Problem Description

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$.

Input Format

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 Format

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

7 9
cats
eel
eve
evil
lee
olive
stack

5

2 2
a
aa

2

6 12
aa
aab
no
on
pets
step

43

Hint

[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