打字机

题目描述

我们有一台有 $N$ 排按键的打字机。从上数第 $i$ 排的按键可以打出字符串 $S_i$ 中的字符。

使用这台键盘输入字符串的方法如下。

首先,选择一个整数 $1 \le k \le N$。

然后,从一个空字符串开始,仅使用从上数第 $k$ 排的按键,输入一个长度恰好为 $L$ 的字符串。

通过这种方式可以输入多少个长度为 $L$ 的字符串?

由于答案可能非常大,请输出对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出:

N L
S_1
S_2
…
S_N

输出格式

输出答案。

样例

2 2
ab
ac

7

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

4 3
abcdefg
hijklmnop
qrstuv
wxyz

1352

5 1000000000
abc
acde
cefg
abcfh
dghi

346462871

请务必输出对 $998244353$ 取模后的答案。

数据范围

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