题目描述

给定一个由非空字符串$s_1,s_2,\ldots,s_M$组成的集合$S$，其中每个字符串的长度至多为$6$，由字符a和b组成。找到长度为$N$且由字符a和b组成的字符串$T$的数量，满足以下条件：

• 对于任何$s_i\in S$，$T$中不包含$s_i$作为连续子串。

由于答案可能非常大，找到结果除以$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<j\leq M)$

输入和输出

从标准输入中按以下格式输入数据：

$N$ $M$ $s_1$ $s_2$ $\vdots$ $s_M$

在单独一行中以$998244353$为模的余数输出结果。

示例

示例输入1

4 3
aab
bbab
abab

示例输出1

10

长度为$4$，由字符a和b组成的字符串中，有$10$个满足不包含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$为模的余数输出结果。