Subway Lines X29412

Ben Zynoulus lives in a city in Meashara. He travels around only by subway. Each subway line is a cycle, thus if you enter at station $s_1$, you will reach $s_2$, then $s_3$, ..., $s_k$, then you return to $s_1$, then to $s_2$, and so on.

Each subway line is unidirectional: you can go from $s_1$ to $s_2$, but not from $s_2$ to $s_1$. In some cases there might be another subway line which goes from $s_2$ to $s_1$; however, Ben has a rule that, after going from $s_1$ to $s_2$, he never goes back directly to $s_1$.

As every subway user, Ben has a card to pay for his tickets, and this card notes the number of stations travelled so far, over all his lifetime. Now, Ben has a question: how many possible routes could he have taken, according to his rules? If there are two subway lines which go from $s_1$ to $s_2$, then he considers routes using them distinct.

Input

Each subway station has a code, which is a lowercase letter of the English alphabet.

The first line contains $N$ ($1 \leq N \leq 5$), the number of subway routes, and $L$ ($1 \leq L \leq 30000000$), the number of stations travelled so far. Each of the following $N$ lines contains a description of one subway route, as a string. These are codes of consecutive stations of the given route.

Output

Output the number of possible routes modulo 1000007.

In this case Ben can travel either a-b-c-d-e-a-..., or e-d-c-b-a-e-... He cannot change between these two options, since he would break his rule. However, in the first case, he can change the subway line he is using after each station. This gives us $5 \cdot (2^{10}+1)$ possible routes in total.