← 返回题目列表

AtCoder · abc305_g

G. 禁止的子字符串

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

分数: 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.