Processing math: 100%

Problem A. Appropriate names

Author:G.Korneev, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

A company wants to name a new product. Marketing department determined, that a name for a product is appropriate, if:

  1. it consist of exactly N small English letters;
  2. it has alternating vowels and consonants;
  3. it does not contain any of given M offensive substrings.

Your program must calculate the number of possible appropriate names. Note that English vowels are: 'a', 'e', 'i', 'o', 'u', 'y'.

Input file format

First line of input file contains two integers NM — name length and number of offensive substrings.

Following M lines contain offensive substrings si, one per line.

Output file format

Output file must contain a single integer — number of appropriate names modulo 109+7.

Constraints

1N50, 0M50, 1length(si)N.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 3
b
ca
b
227
2
5 0
374400

0.066s 0.009s 13