시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 2048 MB1000.000%

문제

Ene loves palindromes.

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

Ene wants to know the number of ways to do this. Two ways are considered different when the sequences of the concatenated interesting words in them are different. Note that multiple different ways may result in the same palindrome. Since the answer may be very large, you need to find the result modulo $10^9 + 7$.

입력

The first line of the input contains two positive integers $N$ and $L$ representing the number of the interesting words and the length of the palindrome to be formed ($1 \le N \le 333$, $1 \le L \le 1000$).

Each of the following $N$ lines contains an interesting word $s_i$ ($1\le |s_i| \le L$, $\sum_{i=1}^N |s_i| \le 600$; the interesting words only contain lowercase English letters and are pairwise distinct).

출력

Output a line with a single integer: the number of ways to form a palindrome modulo $10^9 + 7$.

예제 입력 1

7 9
cats
eel
eve
evil
lee
olive
stack

예제 출력 1

5

예제 입력 2

2 2
a
aa

예제 출력 2

2

예제 입력 3

6 12
aa
aab
no
on
pets
step

예제 출력 3

43

노트

In the first example, the five different ways are the following:

stack cats; evil olive; eel eve lee; lee eve eel; eve eve eve.