102465: [AtCoder]ABC246 F - typewriter

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$.

问题描述

我们有一个具有 N 排按键的打字机。从顶部算起的第 i 排按键可以输入字符串 S_i 中的字符。

我们使用这个键盘输入一个字符串，如下所示。

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

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

约束条件

• N 和 L 是整数。
• 1≤N≤18
• 1≤L≤10^9
• S_i 是 abcdefghijklmnopqrstuvwxyz 的一个（不一定连续的）非空子序列。

输入

输入数据以以下格式从标准输入给出：

N L
S_1
S_2
…
S_N

输出

输出答案。

样例输入 1

2 2
ab
ac

样例输出 1

7

我们可以输入七种字符串：aa、ab、ac、ba、bb、ca、cc。

样例输入 2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

样例输出 2

1352

样例输入 3

5 1000000000
abc
acde
cefg
abcfh
dghi

样例输出 3

346462871

请确保输出答案模 998244353 的结果。