typewriter

题目描述

我们有一个有 $N$ 行的打字机。第 $i$ 行（从上数）上的按键可以输入字符串 $S_i$ 中的字符。 用这个键盘输入一个字符串，方式如下。

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

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

输入格式

输入按如下格式从标准输入给出： $N$ $L$ $S_1$ $S_2$ $\dots$ $S_N$

输出格式

输出答案。

2 2
ab
ac

7

4 3
abcdefg
hijklmnop
qrstuv
wxyz

1352

5 1000000000
abc
acde
cefg
abcfh
dghi

346462871

提示

$N$ 和 $L$ 是整数。 $1 \le N \le 18$ $1 \le L \le 10^9$ $S_i$ 是 $abcdefghijklmnopqrstuvwxyz$ 的一个（不一定连续的）非空子序列。我们可以输入七个字符串： $aa$、$ab$、$ac$、$ba$、$bb$、$ca$、$cc$。
请确保对 $998244353$ 取模后输出答案。

标签: AtCoder|abc246F

来源

AtCoder|abc246F