Fantastic Fožgaj

Time limit1.5sMemory limit512 MB

Summary

Count length-m lowercase strings over 26 letters that avoid any of n forbidden patterns as a substring, modulo 1e9+7, with m up to 1e9.

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

Problem

Fožgaj wants to become friends with Dodo, so he has decided to compose a speech about friendship.

Fožgaj's speech is a word consisting of (m) lowercase letters of the English alphabet. Domagoj (who has already heard one speech about friendship from Fožgaj) knows that there is a list of (n) words that could frighten little Dodo.

Mr. Malnar managed to obtain that list for Fožgaj, and now Fožgaj wonders how many different words of length (m) exist in which none of the words from the list appears. A word from the list appears in Fožgaj's speech if it is present in it as a sequence of consecutive characters.

Help Fožgaj and print how many different words of length (m) exist in which none of the words from the list appears, modulo (10^9 + 7).

Input

The first line contains the natural numbers (n) ((1 \le n \le 100)) and (m) ((1 \le m \le 10^9)) from the problem statement.

Each of the following (n) lines contains one word from Domagoj's list. The words in the list consist of lowercase letters of the English alphabet and do not repeat. Also, the sum of the lengths of all words is at most 100.

Output

Print the required number from the problem statement on a single line.

Examples3

Example 1
Input
```
2 1
a
b
```
Expected output
```
24
```
Example 2
Input
```
3 2
a
ba
bb
```
Expected output
```
624
```
Example 3
Input
```
4 10
wa
tle
mle
sigsegv
```
Expected output
```
798986899
```