分数: 550 点
问题陈述
给你一套 S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace 长度的非空字符串 6 组成 a 和 b。
求字符串的个数 T 长度 N 组成 a 和 b 满足以下条件:
- T 不包含 s _ i 作为任意的连续子字符串 s _ i\in S.
由于答案可能很大,请对它求模 998244353.
约束
- 1\leq N\leq10^{18}
- 1\leq M\leq126
- N 和 M 是整数。
- s _ i 是一个最大长度的非空字符串 6 组成
a和b. - s _ i\neq s _ j\ (1\leq i\lt j\leq M)
输入
输入由标准输入按以下格式给出:
N M s _ 1 s _ 2 \vdots s _ M
输出
打印答案模数 998244353 在一行中。
示例输入 1
4 3 aab bbab abab
示例输出 1
10
有 10 长度的字符串 4 组成 a 和 b 不包含 aab, bbab,或 abab 作为连续子字符串: aaaa, abaa, abba, abbb, baaa, baba, babb, bbaa, bbba,和 bbbb。因此,您应该打印 10.
示例输入 2
20 1 aa
示例输出 2
17711
示例输入 3
1000000007 28 bbabba bbbbaa aabbab bbbaba baaabb babaab bbaaba aabaaa aaaaaa aabbaa bbaaaa bbaabb bbabab aababa baaaba ababab abbaba aabaab ababaa abbbba baabaa aabbbb abbbab baaaab baabbb ababbb baabba abaaaa
示例输出 3
566756841
打印答案模数 998244353.