Problem Background

This problem is a translation from CERC 2019 "K==S"

Problem Description

Progressive hard octave rock tunes (so-called "phorts") are created using specific notes. This rock style is based solely on 13 different note pitches, and other pitches (in other octaves) are considered outdated musical foundations. Each note can be either long or short. Therefore, there are exactly 26 different notes in rock.

You will compose a phort tune for your friend's birthday and perform it with your band in the main city square. When creating the suffix, you need to avoid using certain musical phrases that are copyrighted due to long-term research sponsored by major record companies. It has been proven that these phrases are very catchy and easy to remember, and can be used to subconsciously associate the audience with a specific music company, which uses these phrases in their productions.

A tune is a sequence of notes. A musical phrase is also a sequence of notes, and it is considered to be included in the tune if its notes form a continuous subsequence of the tune, meaning the same notes appear in the same order in the tune.

Fortunately, only a few banned phrases have been patented so far. Therefore, you can relatively freely compose your own tune. In particular, you are interested in the number of acceptable tunes of certain lengths. An acceptable tune is any tune that does not contain a banned phrase. The length of a tune is equal to the number of notes it contains.

Input Format

The first line contains two integers \( N, Q \) \((1 \le N \le 10^9, 1 \le Q \le 100)\). \( N \) is the length of the tune, and \( Q \) is the number of banned musical phrases.

The next \( Q \) lines each describe a banned phrase. The description of a banned phrase starts with a positive integer \( L \) indicating its length, followed by a string of \( L \) lowercase English letters. Each letter represents a rock note, and different letters represent different notes.

The total length of all banned phrases does not exceed 100.

Output Format

Output the number of different acceptable tunes of length \( N \) modulo \( 1\,000\,000\,007 \).

Sample Input and Output

Sample Input #1

2 3
1 a
1 b
1 c

Sample Output #1

529

Sample Input #2

3 3
2 aa
1 a
1 a

Sample Output #2

15625

Sample Input #3

3 1
2 ab

Sample Output #3

17524

见题面 Input 部分

见题面 Output 部分