Score : $550$ points

问题描述

给定一个包含长度最多为6个由字符a和b组成的非空字符串集合 $S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace$。要求找出满足以下条件的长度为 $N$ 的仅包含字符a和b的字符串 $T$ 的数量：

• 对于集合 $S$ 中的所有 $s _ i$，字符串 $T$ 都不含有连续子串 $s _ i$。

由于答案可能非常大，请计算结果对 $998244353$ 取模后的值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a set $S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace$ of non-empty strings of length at most $6$ consisting of a and b. Find the number of strings $T$ of length $N$ consisting of a and b that satisfy the following condition:

• $T$ does not contain $s _ i$ as a consecutive substring for any $s _ i\in S$.

Since the answer can be enormous, find it modulo $998244353$.

Constraints

• $1\leq N\leq10^{18}$
• $1\leq M\leq126$
• $N$ and $M$ are integers.
• $s _ i$ is a non-empty string of length at most $6$ consisting of a and b.
• $s _ i\neq s _ j\ (1\leq i\lt j\leq M)$

Input

The input is given from Standard Input in the following format:

$N$ $M$

$s _ 1$

$s _ 2$

$\vdots$

$s _ M$

Output

Print the answer modulo $998244353$ in a single line.

Sample Input 1

4 3
aab
bbab
abab

Sample Output 1

10

There are $10$ strings of length $4$ consisting of a and b that do not contain aab, bbab, or abab as consecutive substrings: aaaa, abaa, abba, abbb, baaa, baba, babb, bbaa, bbba, and bbbb. Thus, you should print $10$.

Sample Input 2

20 1
aa

Sample Output 2

17711

Sample Input 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

Sample Output 3

566756841

Print the answer modulo $998244353$.

update @ 2024/3/10 08:37:09