Palindrome Word Sequences

A palindrome is a string that reads the same forward and backward.

You are given N distinct uppercase English words. Count how many ways there are to concatenate the given words, in any order, so that the resulting string has length L and is a palindrome.

Each word may be used more than once. If two sequences of chosen words are different, they are counted as different ways even when their concatenated string is identical.

The first line contains N, the number of words. The second line contains L, the required length of the final string. Each of the next N lines contains one distinct uppercase English word.

• 1 <= N <= 50
• 1 <= L <= 30
• Each word has length between 1 and 15, inclusive.
• Every word consists only of uppercase English letters.

Print the number of ways to concatenate the given words into a palindrome of length L. The answer does not exceed 2,100,000,000.