Count Palindromic Word Sequences

Time limit2sMemory limit128 MB

Summary

Count ordered sequences of given words, space-joined, whose concatenation (ignoring spaces) is a palindrome of length at most K, modulo a prime.

Level: Hard8 of 10
Topics: Dynamic programming, String matching, String, Combinatorics
Solved: No attempts yet

Problem

A palindrome is a string that reads the same from left to right and from right to left. In this problem, all spaces are ignored when deciding whether a string is a palindrome.

You are given N distinct words. You may choose words and arrange them in order to make a string S. A word may be used multiple times, and some words may be unused. Exactly one space must be placed between adjacent words, including between two equal consecutive words. S may not start or end with a space.

Count the strings S that can be made this way such that, after ignoring spaces, S is a palindrome and the total length of S is at most K. Spaces between words are included in the length. The empty string is not counted.

Input

The first line contains the number of words N and the length limit K. Both are positive integers, with N <= 50 and K <= 100.

Each of the next N lines contains one word. Every word consists only of lowercase English letters, has length at most 15, and no word appears more than once.

Output

Print the number of valid strings S, modulo 835454957.

Note

In the first public test case, exactly 5 strings satisfy the conditions within the length limit.

Examples4

Example 1
Input
```
2 4
z
zz
```
Expected output
```
5
```

Example 2

Input

7 70
aba
acaba
baca
cac
b
c
a

Expected output

370786966

Example 3
Input
```
1 100
hello
```
Expected output
```
0
```
Example 4
Input
```
2 24
tragic
cigar
```
Expected output
```
1
```