Progressive hard octave rock tunes (so-called “phorts”) are written using a specific music notation. 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. \InputFile 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, $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$. \OutputFile Output the number of different acceptable tunes of length $n$. Print the result modulo $10^9 + 7$.