Palindrome Construction

Ene loves palindromes. Ene now has some words. She wants to select some words (each word may be chosen any number of times, including zero) and concatenate them in order to form a palindrome whose total length is exactly $L$. Two ways are considered different if and only if the counts of each word used or their order of arrangement differs (note that different ways may result in the same palindrome). Since the answer can be very large, output it modulo $1{,}000{,}000{,}007$.

A sequence forms a palindrome if it reads the same backward as forward. In other words, if the sequence of words is $w_1, w_2, \dots, w_k$ (or $w_1, w_2, \dots, w_k, c, \tilde{w}_k, \dots, \tilde{w}_1$ in the odd case), then it must satisfy that for each word chosen in the left half, its mirror image (i.e. the reverse of the word) appears in the corresponding position of the right half. Note that a word can serve as the center of the palindrome only if it is itself a palindrome (i.e. $w=\text{reverse}(w)$).

The formation of a palindrome can be broken down into two cases:

1. Even-length palindrome: Choose a sequence of words (possibly empty) for the left half. The right half is uniquely determined by taking the reverse (characterwise) of that left sequence. The total length condition becomes: [ 2\times(\text{sum of lengths of words in the left half}) = L. ]

2. Odd-length palindrome: Choose a word to serve as the center (which must be a palindrome itself), and choose a sequence of words for the left half. The right half is then the reverse of the left half. The total length condition becomes: [ 2\times(\text{sum of lengths of words in the left half}) + (\text{length of center word}) = L. ]

You are given $n$ words and an integer $L$. Calculate the number of ways to form a palindrome of length exactly $L$ as described above, modulo $1{,}000{,}000{,}007$.

Input Format: The input begins with two integers $n$ and $L$. Then follow $n$ lines, each containing a word. Each word is a non-empty string comprised of lowercase English letters.

Output Format: Print a single integer, the number of ways modulo $1{,}000{,}000{,}007$.

inputFormat

The first line contains two integers $n$ and $L$ ($1 \leq n \leq 100$, $0 \leq L \leq 1000$), the number of words and the desired length of the palindrome. The following $n$ lines each contain a non-empty string consisting of lowercase English letters, representing the available words.

outputFormat

Output a single integer: the number of ways to form a palindrome of length exactly $L$, taken modulo $1{,}000{,}000{,}007$.

sample

1 1
a

1