← 返回题目列表

AtCoder · abc458_f

F. 严重误读

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

你被给予 K 字符串 S_i 由小写英文字母组成。
求模数 998244353,长度为字符串 N 由小写英文字母组成,不包含任何 S_1, S_2, \dots, S_K 作为子字符串(连续子序列)。

约束

  • N 是介于 1 和 10^9,包括在内。
  • K 是介于 1 和 10,包括在内。
  • S_i 是由小写英文字母组成的字符串,长度介于 1 和 10,包括在内。

输入

输入由标准输入按以下格式给出:

N K
S_1
S_2
\vdots
S_K

输出

输出答案。


示例输入 1

3 2
aa
ab

示例输出 1

17474
  • 长度的字符串数量 3 由小写英文字母组成的是 26^3=17576.
  • 长度的字符串数量 3 由小写英文字母组成,前两个字符为 aa is 26.
  • 长度的字符串数量 3 由小写英文字母组成,最后两个字符为 aa is 26.
  • 长度的字符串数量 3 由小写英文字母组成,前两个字符为 ab is 26.
  • 长度的字符串数量 3 由小写英文字母组成,最后两个字符为 ab is 26.
  • 长度的字符串数量 3 由小写英文字母组成,其整体为 aaa is 1.
  • 长度的字符串数量 3 由小写英文字母组成,其整体为 aab is 1.
  • 结合以上事实,可以确认该测试用例的答案是 17474.

示例输入 2

1 1
ab

示例输出 2

26

示例输入 3

1000000000 10
contest
tester
error
orange
angel
elegant
antitese
sextuple
pleasure
surely

示例输出 3

698570468

求计数模数 998244353.