当前没有测试数据。

F - 打字机

得分：500分

问题描述

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

我们使用这个键盘输入字符串，按照如下方式：

• 首先，选择一个整数 $1 \le k \le N$。
• 然后，从空字符串开始，只能使用第 $k$ 行从上到下的按键输入一个长度为 $L$ 的字符串。

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

约束

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

输入

从标准输入中按照以下格式给出输入：

$N$ $L$

$S_1$

$S_2$

$\dots$

$S_N$

输出

输出答案。

2 2
ab
ac

7

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

4 3
abcdefg
hijklmnop
qrstuv
wxyz

1352

5 1000000000
abc
acde
cefg
abcfh
dghi

346462871

请确保输出结果对 $998244353$ 取模。