F - All Included 解説 /

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

配点 : 550 点

問題文

N 個の英小文字列 S_1,S_2,\ldots,S_N および整数 L が与えられます。

長さ L の英小文字列であって、S_1,S_2,\ldots,S_N をすべて部分文字列として含むものの個数を 998244353 で割った余りを求めてください。

部分文字列とは S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab, bc, bcd は abcd の部分文字列ですが、ac, dc, e は abcd の部分文字列ではありません。

制約

  • 1\leq N\leq 8
  • 1\leq L\leq 100
  • N,L は整数
  • S_i は長さが 1 以上 10 以下の英小文字からなる文字列
  • S_i\neq S_j\ (i\neq j)

入力

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

N L
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

2 4
ab
c

出力例 1

153

条件を満たす文字列として、たとえば abcz や cabc があります。acbd は ab を部分文字列として含まないため条件を満たしません。

入力例 2

2 6
abc
cde

出力例 2

54

入力例 3

5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj

出力例 3

689020583

Score : 550 points

Problem Statement

You are given N lowercase English strings S_1,S_2,\ldots,S_N, and an integer L.

Find the number, modulo 998244353, of length-L lowercase English strings that contain all of S_1,S_2,\ldots,S_N as substrings.

What is a substring? A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

  • 1\leq N\leq 8
  • 1\leq L\leq 100
  • N and L are integers.
  • Each S_i is a string of length 1 and 10, inclusive, consisting of lowercase English letters.
  • S_i\neq S_j\ (i\neq j)

Input

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

N L
S_1
S_2
\vdots
S_N

Output

Output the answer.

Sample Input 1

2 4
ab
c

Sample Output 1

153

Some of the strings that satisfy the condition are abcz and cabc. acbd does not contain ab as a substring, so it does not satisfy the condition.

Sample Input 2

2 6
abc
cde

Sample Output 2

54

Sample Input 3

5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj

Sample Output 3

689020583