G - Banned Substrings 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 550

問題文

a, b からなる長さ 6 以下の空でない文字列の集合 S=\lbrace s _ 1,s _ 2,\ldots,s _ M\rbrace が与えられます。 以下の条件を満たす a, b からなる長さ N の文字列 T はいくつあるか求めてください。

  • 任意の s _ i\in S に対して、Ts _ i を連続する部分文字列として含まない

ただし、答えは非常に大きくなる可能性があるので、答えを 998244353 で割った余りを求めてください。

制約

  • 1\leq N\leq10^{18}
  • 1\leq M\leq126
  • N,M は整数
  • s _ ia, b からなる長さ 6 以下の空でない文字列
  • s _ i\neq s _ j\ (1\leq i\lt j\leq M)

入力

入力は以下の形式で標準入力から与えられる。

N M
s _ 1
s _ 2
\vdots
s _ M

出力

答えを 998244353 で割ったあまりを 1 行で出力せよ。


入力例 1

4 3
aab
bbab
abab

出力例 1

10

a, b からなる長さ 4 の文字列で、連続する部分列として aab, bbab, abab をもたないようなものは aaaa, abaa, abba, abbb, baaa, baba, babb, bbaa, bbba, bbbb10 個なので、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

998244353 で割ったあまりを出力してください。

Score : 550 points

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.