当前没有测试数据。

G - 禁止的子字符串

得分：$550$ 分

问题描述

给定一个由非空字符串 $S = \lbrace s _ 1, s _ 2, \ldots, s _ M\rbrace$ 组成的集合，字符串的长度不超过 $6$，只由字符 a 和 b 构成。 计算所有长度为 $N$ 由字符 a 和 b 构成的字符串的数量 $T$，满足以下条件：

• 对于任意 $S$ 中的 $s _ i$，$T$ 不包含 $s _ i$ 作为连续子串。

由于答案可能非常大，输出结果需要模 $998244353$。

约束

• $1\leq N\leq10^{18}$
• $1\leq M\leq126$
• $N$ 和 $M$ 是整数。
• $s _ i$ 是由字符 a 和 b 构成的非空字符串，长度不超过 $6$。
• $s _ i\neq s _ j\ (1\leq i\lt j\leq M)$

输入

从标准输入中按以下格式给出输入：

$N$ $M$

$s _ 1$

$s _ 2$

$\vdots$

$s _ M$

输出

将答案模 $998244353$ 输出到一行。

4 3
aab
bbab
abab

10

长度为 $4$ 由字符 a 和 b 构成的字符串中，不包含连续子串 aab，bbab 或 abab 的共有 $10$ 个，分别为： aaaa，abaa，abba，abbb，baaa，baba，babb，bbaa，bbba 和 bbbb。因此，输出结果应为 $10$。

20 1
aa

17711

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

566756841

将答案模 $998244353$ 输出。