题目描述

给定 $K$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_K$。

求长度为 $N$ 的由小写英文字母组成的字符串中,不包含 $S_1, S_2, \ldots, S_K$ 中任何一个作为子串(连续子序列)的字符串的数量。

答案对 $998244353$ 取模。

输入格式

N K
S_1
S_2
...
S_K

输出格式

输出答案模 $998244353$。

数据范围

• $1 \le N \le 10^9$
• $1 \le K \le 10$
• $S_i$ 是由小写英文字母组成的字符串。
• $1 \le |S_i| \le 10$

样例 1 输入

3 2
aa
ab

样例 1 输出

17474

• 长度为 $3$ 的小写字母字符串共有 $26^3 = 17576$ 个。
• 减去包含 aa 或 ab 作为子串的字符串数后,得 $17474$。

样例 2 输入

1 1
ab

样例 2 输出

26

(长度为 $1$ 的字符串都不可能包含长度为 $2$ 的 ab。)

样例 3 输入

1000000000 10
contest
tester
error
orange
angel
elegant
antitese
sextuple
pleasure
surely

样例 3 输出

698570468