Score : $500$ points

问题陈述

我们有一个包含 $N$ 行的打字机。从上到下第 $i$ 行的按键可以输入字符串 $S_i$ 中的字符。

现在让我们使用这个键盘按照以下方式输入一个字符串。

• 首先，选择一个整数 $1 \le k \le N$。
• 然后，从一个空字符串开始，仅使用从顶部数起第 $k$ 行的按键输入一个长度恰好为 $L$ 的字符串。

有多少个长度为 $L$ 的字符串可以通过这种方式输入？由于答案可能非常大，请输出结果对 $998244353$ 取模的结果。

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

Problem Statement

We have a typewriter with $N$ rows. The keys in the $i$-th row from the top can type the characters in a string $S_i$.

Let us use this keyboard to enter a string, as follows.

• First, choose an integer $1 \le k \le N$.
• Then, start with an empty string and only use the keys in the $k$-th row from the top to enter a string of length exactly $L$.

How many strings of length $L$ can be entered in this way? Since the answer can be enormous, print it modulo $998244353$.

Constraints

• $N$ and $L$ are integers.
• $1 \le N \le 18$
• $1 \le L \le 10^9$
• $S_i$ is a (not necessarily contiguous) non-empty subsequence of abcdefghijklmnopqrstuvwxyz.

Input

Input is given from Standard Input in the following format:

$N$ $L$

$S_1$

$S_2$

$\dots$

$S_N$

Output

Print the answer.

Sample Input 1

2 2
ab
ac

Sample Output 1

7

We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.

Sample Input 2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

Sample Output 2

1352

Sample Input 3

5 1000000000
abc
acde
cefg
abcfh
dghi

Sample Output 3

346462871

Be sure to print the answer modulo $998244353$.

update @ 2024/3/10 10:33:54