F - Critical Misread 解説 /

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

配点 : 525 点

問題文

英小文字からなる K 個の文字列 S_i が与えられます。
英小文字からなる長さ N の文字列であって、 S_1,S_2,\dots,S_K のいずれも部分文字列 (連続する部分列) として含まないものの個数を 998244353 で割った余りを求めてください。

制約

  • N は 1 以上 10^9 以下の整数
  • K は 1 以上 10 以下の整数
  • S_i は英小文字からなる長さ 1 以上 10 以下の文字列

入力

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

N K
S_1
S_2
\vdots
S_K

出力

答えを出力せよ。

入力例 1

3 2
aa
ab

出力例 1

17474
  • 英小文字からなる長さ 3 の文字列は 26^3=17576 個あります。
  • 英小文字からなる長さ 3 の文字列のうち先頭 2 文字が aa であるものは 26 個あります。
  • 英小文字からなる長さ 3 の文字列のうち末尾 2 文字が aa であるものは 26 個あります。
  • 英小文字からなる長さ 3 の文字列のうち先頭 2 文字が ab であるものは 26 個あります。
  • 英小文字からなる長さ 3 の文字列のうち末尾 2 文字が ab であるものは 26 個あります。
  • 英小文字からなる長さ 3 の文字列のうち全体が aaa であるものは 1 個あります。
  • 英小文字からなる長さ 3 の文字列のうち全体が aab であるものは 1 個あります。
  • 以上の事柄を組み合わせることで、このテストケースに対する答えが 17474 であることが確認できます。

入力例 2

1 1
ab

出力例 2

26

入力例 3

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

出力例 3

698570468

998244353 で割った余りを求めてください。

Score : 525 points

Problem Statement

You are given K strings S_i consisting of lowercase English letters.
Find the number, modulo 998244353, of strings of length N consisting of lowercase English letters that do not contain any of S_1, S_2, \dots, S_K as a substring (contiguous subsequence).

Constraints

  • N is an integer between 1 and 10^9, inclusive.
  • K is an integer between 1 and 10, inclusive.
  • S_i is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Input

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

N K
S_1
S_2
\vdots
S_K

Output

Output the answer.

Sample Input 1

3 2
aa
ab

Sample Output 1

17474
  • The number of strings of length 3 consisting of lowercase English letters is 26^3=17576.
  • The number of strings of length 3 consisting of lowercase English letters whose first two characters are aa is 26.
  • The number of strings of length 3 consisting of lowercase English letters whose last two characters are aa is 26.
  • The number of strings of length 3 consisting of lowercase English letters whose first two characters are ab is 26.
  • The number of strings of length 3 consisting of lowercase English letters whose last two characters are ab is 26.
  • The number of strings of length 3 consisting of lowercase English letters whose entirety is aaa is 1.
  • The number of strings of length 3 consisting of lowercase English letters whose entirety is aab is 1.
  • Combining the above facts, it can be confirmed that the answer for this test case is 17474.

Sample Input 2

1 1
ab

Sample Output 2

26

Sample Input 3

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

Sample Output 3

698570468

Find the count modulo 998244353.