分数: 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 由小写英文字母组成,前两个字符为
aais 26. - 长度的字符串数量 3 由小写英文字母组成,最后两个字符为
aais 26. - 长度的字符串数量 3 由小写英文字母组成,前两个字符为
abis 26. - 长度的字符串数量 3 由小写英文字母组成,最后两个字符为
abis 26. - 长度的字符串数量 3 由小写英文字母组成,其整体为
aaais 1. - 长度的字符串数量 3 由小写英文字母组成,其整体为
aabis 1. - 结合以上事实,可以确认该测试用例的答案是 17474.
示例输入 2
1 1 ab
示例输出 2
26
示例输入 3
1000000000 10 contest tester error orange angel elegant antitese sextuple pleasure surely
示例输出 3
698570468
求计数模数 998244353.