[CERC2019] K==S

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