Description

Original source: JSOI 2007

JSOI assigned team member ZYX the task of developing a computer program called a "Text Generator": the users of this software are young children who currently use GW Text Generator v6. This software can randomly generate articles—always producing a fixed-length and completely random article, meaning every byte in the generated article is entirely random. An article is considered readable if it contains at least one word known to the users (we say article $a$ contains word $b$ if and only if word $b$ is a substring of article $a$).

However, even by this standard, the articles generated by GW Text Generator v6, which the users currently use, are almost entirely unreadable. ZYX needs to determine the number of readable texts among all possible texts generated by GW Text Generator v6 to successfully obtain the v7 update. Can you help him?

Input Format

The first line of input contains two positive integers: the total number of words known by the users $N$, and the fixed length $M$ of the text generated by GW Text Generator v6;

The following $N$ lines each contain a word known by the users.

Output Format

An integer representing the total number of possible articles. Only the result modulo $10007$ is required.

Sample 1

2 2
A
B

100

Data Range and Hint

For all data, $1\le N\le 60$, the length of all words and the text will not exceed $100$, and they may only contain uppercase English letters.