Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2019
K==S
kequalss.c, kequalss.cpp, Kequalss.java, kequalss.py
Progressive hard octave rock tunes (so-called "phorts") are written using a specific music nota-
tion. This flavor of rock is built on just 13 different note pitches, other pitches (in other octaves)
are considered to be an outdated musical ballast. Each note can be either a long one or a short
one. Consequently, there are exactly 26 different notes in the rock.
You are going to compose a phort tune on the occasion of your friend's birthday and perform it
with your band on the main town square. While composing the phort, you need to avoid certain
musical phrases, which are heavily copyrighted as a result of long research sponsored by big
record companies. It has been established that these phrases are very catchy, easy to remember,
and could be exploited to bind the listeners subconsciously to a particular music company which
would utilize these phrases in their production.
The tune is a sequence of notes. A musical phrase is also a sequence of notes and it is considered
to be contained in a tune if its notes form a contiguous subsequence of the tune, which means
the same notes appear in the tune right after each other in the same order.
Fortunately, only a few forbidden phrases have been patented so far. Thus, you have a relative
freedom in composing your own tunes. In particular, you are interested in the number of
acceptable tunes of some length. An acceptable tune is any tune which does not contain a
forbidden phrase. The length of the tune is equal to the number of notes it contains.
Input Specification
The first line contains two integers N , Q (1 ≤ N ≤ 109, 1 ≤ Q ≤ 100). N is the length of the
tune, Q is the number of forbidden musical phrases. Each of the Q following lines describes one
forbidden phrase. A description of a forbidden phrase starts with a positive integer L, indicating
its length, followed by a string of L lowercase English letters. Each letter represents one rock
note, different letters represent different notes.
The sum of lengths of all forbidden phrases does not exceed 100.
Output Specification
Output the number of different acceptable tunes of length N . Print the result modulo 1 000 000 007.
Output for Sample Input 1
Sample Input 1
529
2
3
1
a
1
b
1
c
Sample Input 2
Output for Sample Input 2
15625
3
3
2
aa
1
a
1
a
Sample Input 3
Output for Sample Input 3
31
17524
2 ab
