Problem F
Danish

Boschua is moving to Lund to study at LTH. You’ve learned that Lund is in Skåne, and now you’re worried that Boschua might start sounding Danish.

To prevent this, you want to show Boschua how many words don’t sound Danish at all. According to you, a word sounds Danish if it contains at least one word from the Danish dictionary. Unfortunately, you don’t have access to the official Danish dictionary, but the old dictionary you found in the basement will have to suffice.

For example, suppose the dictionary only contains the word knallert. Then you consider the word husknallertrumma to sound Danish because it contains the word knallert. On the other hand, you consider the word knallerunt to not sound Danish because it does not contain knallert.

Figure 1: The word husknallertrumma sounds Danish.

Figure 2: The word knallerunt does not sound Danish.

You quickly realize there are too many words that don’t sound Danish to list them all. Thus, you decide it’s sufficient to count the number of words that don’t sound Danish and share that with Boschua. Even this turns out to be difficult since there are so many words that don’t sound Danish.

Finally, you settle for counting the number of words that consist of only lowercase English letters a-z, have exactly $N$ letters, and don’t sound Danish. A word sounds Danish if it contains at least one word from the dictionary as a substring.

Input

The first line of input contains the integers $N$ ($1 \leq N \leq 100$) and $M$ ($0 \leq M \leq 150$), the length of the words being considered and the number of words in the dictionary.

The following $M$ lines each contain a word from the dictionary. All these words have a length of at most $N$ and consist of the letters a-z. All words in the dictionary are unique.

Output

Print the number of words of length $N$ that don’t sound too Danish. Since this number can be very large, output it modulo $10^9+7$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Samples

In the first sample, there are $26^3$ different words. Since the Danish dictionary is empty in this case, none of them are forbidden.

3 0

17576

2 2
a
po

624

5 5
java
py
js
rust
apl

11738952