禁用子串

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定 $M$ 个互不相同的非空字符串 $s_1,s_2,\ldots,s_M$。每个字符串都只由字符 a 和 b 组成，且长度不超过 $6$。

求有多少个字符串 $T$ 同时满足：

• $T$ 的长度为 $N$，且只由字符 a 和 b 组成；
• 对每个 $1\le i\le M$，$T$ 都不包含 $s_i$ 作为连续子串。

答案对 $998244353$ 取模。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含字符串 $s_i$。

输出格式

输出一个整数，表示满足条件的字符串数量对 $998244353$ 取模后的结果。

样例输入 1

4 3
aab
bbab
abab

样例输出 1

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

数据范围

对于所有数据：

• $1\le N\le10^{18}$；
• $1\le M\le126$；
• $1\le |s_i|\le6$；
• $s_i$ 只包含字符 a 和 b；
• 任意两个给定字符串互不相同。