Phort Tunes Counting Problem

In phort style, music is composed using exactly 26 distinct notes. A phort tune is a sequence of notes that does not contain any forbidden musical phrases as contiguous subsequences. A forbidden phrase is defined as a sequence of notes that cannot appear in the tune due to copyright restrictions. Given an integer \(n\) representing the length (number of notes) of the tune, and \(m\) forbidden phrases, count the number of acceptable tunes of length \(n\) that do not contain any forbidden phrase. The answer may be very large, so output it modulo \(10^9+7\).

Note: Each note is represented by an uppercase English letter from 'A' to 'Z'.

inputFormat

The first line contains an integer \(n\) (the length of the tune).

The second line contains an integer \(m\), the number of forbidden phrases.

Each of the following \(m\) lines contains a non-empty string of uppercase letters representing a forbidden phrase.

outputFormat

Output a single integer: the number of acceptable tunes of length \(n\) modulo \(10^9+7\).

sample

1
1
AB

26