Count Readable Random Texts

A computer program called the "Text Generator" generates random texts of a fixed length n. Each text is produced by choosing each character uniformly at random from the 26 lowercase English letters. A text is called readable if it contains at least one of a given set of m words (each word is a contiguous substring in the text). For example, a text s is said to contain a word t if and only if t appears consecutively in s.

You are given the length of the text, n, and m words. Your task is to determine the total number of texts that are readable, i.e. those that contain at least one of the given words, modulo \(10^4+7\) (i.e. modulo 10007).

Input Constraints:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 100\)
• Each of the m words is non-empty and consists only of lowercase English letters.

Note: It is recommended to solve this problem using techniques such as the Aho-Corasick automaton combined with dynamic programming.

inputFormat

The first line contains two integers n and m — the length of the text and the number of words, respectively.

Each of the following m lines contains a non-empty word comprised of lowercase English letters.

outputFormat

Output a single integer representing the number of readable texts (i.e. texts that contain at least one of the given words as a substring), modulo \(10^4+7\) (which is 10007).

sample

2 1
ab

1