Microgene

sevenzero is very interesting in Bioinformation and have done some research on it. One day, sevenzero found a phenomenon called Microgene. Microgene is a special fragment in the DNA, and different Microgenes may have the same hereditary effect. Microgene works if and only if there are more than one Microgenes(Microgenes may overlap) with the same hereditary effect in the DNA. To finish his paper, sevenzero wants to know how many different DNAs with length L which contain the hereditary effect caused by Microgenes.

To simplify the problem, a DNA or a Microgene is considerd as a string consisting of character 'A', 'T', 'C' and 'G'. And a Microgene is in the DNA if the Microgene string is the substring of the DNA string. All Microgenes given are different and with the same hereditary effect.

There are several test cases in the input. Each case begins with a line with an integer N (1 ≤ N ≤ 6) and L (1 ≤ N ≤ 1000000), denoting the number of Microgenes and the length of DNA. The following N lines contain N strings representing the Microgenes.The length of the Microgene is no more than 5. The input is terminated by EOF.

One line for each case, the answer modulo 10007.

2 3
AT
TC
2 3
ATC
T
3 1000000
ATCG
TCGT
CTAG

1
11
5063

2011 Multi-University Training Contest 13 - Host by HIT