Viruses
In a certain antivirus company, researchers are studying viruses. They have identified m types of viruses, each represented by a unique string of lowercase Latin letters. Different virus types correspond to different strings.
The researchers are now focusing on a new subject: fully infected strings. A string s is considered fully infected if, for every character in s, there exists a substring of s that includes this character and matches one of the virus strings.
Your task is to determine the number of fully infected strings of length n, given the virus strings. Since this number can be extremely large, you should output it modulo 10^9+7.
Input
The first line contains two integers n and m (1 ≤ n ≤ 400; 1 ≤ m ≤ 20).
The following m lines each contain a description of a virus, consisting of a sequence of lowercase Latin letters.
Each virus string has a positive length that does not exceed 20 characters.
Output
Output a single integer — the remainder when the number of fully infected strings is divided by 10^9+7.