{"problem":{"name":"[CERC2019] K==S","description":{"content":"渐进式硬八度摇滚曲调（所谓的“phorts”）是使用特定的音符创作的。这种摇滚风格只建立在 $13$ 个不同的音符音高上，其他音高（在其他八度中）被认为是过时的音乐基石。每个音符可以是长的，也可以是短的。因此，摇滚中正好有 $26$ 个不同的音符。 你将在你朋友的生日之际创作一首 phort 曲调，并与你的乐队在主要的城市广场上表演。在创作词缀时，你需要避免使用某些音乐短语，这些短语由于大型唱片","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9613"},"statements":[{"statement_type":"Markdown","content":"渐进式硬八度摇滚曲调（所谓的“phorts”）是使用特定的音符创作的。这种摇滚风格只建立在 $13$ 个不同的音符音高上，其他音高（在其他八度中）被认为是过时的音乐基石。每个音符可以是长的，也可以是短的。因此，摇滚中正好有 $26$ 个不同的音符。\n\n你将在你朋友的生日之际创作一首 phort 曲调，并与你的乐队在主要的城市广场上表演。在创作词缀时，你需要避免使用某些音乐短语，这些短语由于大型唱片公司赞助的长期研究而受到版权保护。已经证实，这些短语非常朗朗上口，易于记忆，可以用来将听众下意识地与某个特定的音乐公司联系起来，该公司会在他们的制作中使用这些短语。\n\n曲调是一连串的音符。一个音乐短语也是一个音符序列，如果它的音符形成曲调的连续子序列，则它被认为包含在曲调中，这意味着相同的音符以相同的顺序出现在曲调中。\n\n幸运的是，到目前为止，只有少数禁用短语获得了专利。因此，你可以相对自由地创作自己的曲调。特别是，您对某些长度的可接受的曲调的数量感兴趣。可接受的曲调是指任何不包含禁用短语的曲调。曲调的长度等于它所包含的音符数。\n\n## Input\n\n第一行包含两个整数 $N, Q\\ (1\\le N\\le 10^9, 1\\le Q\\le 100)$。$N$ 是曲调的长度，$Q$ 是禁用音乐短语的数量。\n\n接下来 $Q$ 行，每行都描述了一个禁用短语。禁用短语的描述以一个表示其长度的正整数 $L$ 开头，后跟一个由 $L$ 个小写英文字母组成的字符串。每个字母代表一个摇滚音符，不同的字母代表不同的音符。\n\n所有禁用短语的长度总和不超过 $100$。\n\n## Output\n\n输出长度为 $N$ 的不同可接受曲调的数量对 $1\\,000\\,000\\,007$ 取模的值。\n\n[samples]\n\n## Background\n\n**题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[K==S](https://contest.felk.cvut.cz/19cerc/solved/kequalss.pdf)」**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9613","tags":["字符串","动态规划 DP","2019","矩阵加速","矩阵乘法","AC 自动机","ICPC","CERC"],"sample_group":[["2 3\n1 a\n1 b\n1 c\n","529\n"],["3 3\n2 aa\n1 a\n1 a\n","15625\n"],["3 1\n2 ab\n","17524\n"]],"created_at":"2026-03-03 11:09:25"}}