# 描述

Given $n$($1 ≤ n ≤ 6$) strings, Mr. B wants to know the number of strings with length $l$, that contain all the given strings as substrings.
As the result might be very large, he wants to know the result modulo $998244353$.
Only the lower case letters are allowed, which means there are $26$ letters.
The length of each given string is at most $6$.

## Input

The first line contains two integers $l$($0 ≤ l ≤ 10 ^ 9$), $n$($1 ≤ n ≤ 6$).
The next $n$ lines contains $n$ strings.

## Output

Output the answer in one line.

Input Output

# 思路

• 建立AC自动机，我们可以得到一个显然（似乎不显然啊0.0和之前做过的CF696D有点像的套路?）的DP。
$dp[s][i][j]$表示$i→j$经过一条边后字符串状态为$s$的方案数。那么有
$$dp[r][i][j] = \sum_{r=s \lor t} \sum_k dp[s][i][k] * dp[t][k][j]$$这样做$l-1$次显然是不行的，使用矩阵快速幂加速。这样复杂度就是$O(2^{2n}\sum \limits_i{|s_i|} \log l)$。
• 由于上面的DP方程有个集合并的卷积式，我们可以考虑对矩阵做快速沃尔什变换（或快速莫比乌斯变换），这样在做矩阵集合并卷积运算时就可以减少复杂度了。

0%