禁止子串

题目描述

给你一个由 a 和 b 组成、长度至多为 $6$ 的非空字符串集合 $S=\lbrace s_1, s_2, \ldots, s_M \rbrace$。 求满足以下条件的由 a 和 b 组成的长度为 $N$ 的字符串 $T$ 的数量:

对于任意 $s_i \in S$,$T$ 都不包含 $s_i$ 作为连续子串。

由于答案可能非常巨大,请对 $998244353$ 取模后输出。

输入格式

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

N M
s_1
s_2
⋮
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$ 取模后输出答案。

数据范围

• $1 \le N \le 10^{18}$
• $1 \le M \le 126$
• $N$ 和 $M$ 是整数。
• $s_i$ 是由 a 和 b 组成、长度至多为 $6$ 的非空字符串。
• $s_i \neq s_j$ $(1 \le i \lt j \le M)$