问题描述

在一个神秘的信息存储核心中，存在着一套由二进制符号流组成的加密协议。这个协议用于生成一系列长度为 $N$ 的数据片段，每个数据片段仅由两种基本符号 a 和 b 组成。然而，某个未知的入侵者已经设定了一组 $M$ 条禁止模式，这些模式代表了存储核心检测到的恶意指令，一旦生成的二进制流中包含这些禁止模式，系统将拒绝该数据片段的存储。

你的任务是计算：在所有可能的长度为 $N$ 的数据片段中，有多少个数据片段不包含任何禁止模式作为连续子串。

由于答案可能非常庞大，你需要对结果取模 $998244353$，然后输出。

输入格式

输入由多行组成：

• 第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 10^{18}$, $1 \leq M \leq 126$）。
• 接下来的 $M$ 行，每行包含一个长度不超过 6 的字符串，表示一个禁止模式。所有字符串均由 a 和 b 组成，并且彼此互不相同。

输出格式

输出一个整数，表示长度为 $N$ 的数据片段中，满足条件的字符串数量，对 $998244353$ 取模后输出。

样例

4 3
aab
bbab
abab

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

说明

对于样例1：

所有长度为 $4$ 的二进制符号流组合如下：

aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb, bbaa, bbab, bbba, bbbb

其中，包含禁止模式 aab, bbab, abab 的序列有：

aaba, abab, bbab

因此，满足条件的序列数量为 10，答案为 10。