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₁, you will reach s₂, then s₃, ..., s_k, then you return to s₁, then to s₂, and so on.

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

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₁ to s₂, 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 ≤ N ≤ 5), the number of subway routes, and L (1 ≤ L ≤ 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 · (2¹⁰+1) possible routes in total.