Background

This problem is translated 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 on exactly $13$ distinct note pitches, and other pitches (in other octaves) are considered outdated cornerstones of music. Each note can be either long or short. Therefore, there are exactly $26$ different notes in this rock.

You are going to compose a phort tune for your friend’s birthday and perform it with your band on the main city square. When composing riffs, you need to avoid using certain musical phrases that are protected by copyright 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 listeners with a particular music company, which will then use 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 contained in the tune if its notes form a contiguous subsequence of the tune, meaning the same notes appear in the tune in the same order.

Fortunately, so far only a small number of forbidden phrases have been patented. Therefore, you can compose your own tune relatively freely. In particular, you are interested in the number of acceptable tunes of some length. An acceptable tune is any tune that does not contain any forbidden phrase. The length of a tune is 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 forbidden musical phrases.

The next $Q$ lines each describe one forbidden phrase. The description of a forbidden phrase starts with a positive integer $L$ denoting its length, followed by a string of $L$ lowercase English letters. Each letter represents a rock note, and different letters represent different notes.

The sum of lengths of all forbidden phrases does not exceed $100$.

Output Format

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

2 3
1 a
1 b
1 c

529

3 3
2 aa
1 a
1 a

15625

3 1
2 ab

17524

Hint

Translated by ChatGPT 5