渐进硬八度摇滚曲调（所谓的“phorts”）是用一种特定的乐谱编写的。这种风格的摇滚乐仅建立在 13 种不同的音高上，其他音高（在其他八度音阶中）被认为是过时的音乐累赘。每个音符可以是长音符，也可以是短音符。因此，在这种摇滚乐中恰好有 26 种不同的音符。

你打算在朋友生日之际创作一首 phort 曲调，并与你的乐队在城市主广场上演奏。在创作 phort 时，你需要避免某些音乐片段（phrases），这些片段由于大型唱片公司资助的长期研究而受到严格的版权保护。研究表明，这些片段非常抓耳、易记，并可能被利用来潜意识地将听众与特定的音乐公司联系起来，而这些公司会在其产品中利用这些片段。

曲调是一个音符序列。音乐片段也是一个音符序列，如果它的音符构成曲调的连续子序列，则认为它包含在曲调中，这意味着相同的音符在曲调中以相同的顺序紧接着出现。

幸运的是，到目前为止只有少数禁用片段被申请了专利。因此，你在创作自己的曲调时拥有相对的自由。特别地，你对某种长度的合格曲调的数量感兴趣。合格的曲调是指任何不包含禁用片段的曲调。曲调的长度等于它所包含的音符数量。

输入格式

第一行包含两个整数 $N, Q$ ($1 \le N \le 10^9, 1 \le Q \le 100$)。$N$ 是曲调的长度，$Q$ 是禁用音乐片段的数量。

接下来的 $Q$ 行中，每行描述一个禁用片段。禁用片段的描述以一个正整数 $L$ 开始，表示其长度，后面跟着一个由 $L$ 个小写英文字母组成的字符串。每个字母代表一个摇滚音符，不同的字母代表不同的音符。

所有禁用片段的长度之和不超过 100。

输出格式

输出长度为 $N$ 的不同合格曲调的数量。输出结果模 $1\,000\,000\,007$ 的余数。

样例

输入样例 1

2 3
1 a
1 b
1 c

输出样例 1

529

输入样例 2

3 3
2 aa
1 a
1 a

输出样例 2

15625

输入样例 3

3 1
2 ab

输出样例 3

17524