AT_abc246_f [ABC246F] typewriter

题目描述

有一个由 $N$ 层组成的打字机。从上到下，第 $i$ 层的按键可以输入字符串 $S_i$ 中包含的字符。

现在你要用这个键盘按照以下规则输入一个字符串：

• 首先，选择一个整数 $1 \leq k \leq N$。
• 然后，从空字符串开始，只能使用第 $k$ 层的按键，输入恰好 $L$ 个字符组成一个字符串。

请问，按照上述规则可以输入多少种长度为 $L$ 的字符串？由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入给出。

$N$ $L$ $S_1$ $S_2$ $\dots$ $S_N$

输出格式

请输出答案。

样例 1

输入

2 2
ab
ac

输出

7

样例 2

输入

4 3
abcdefg
hijklmnop
qrstuv
wxyz

输出

1352

样例 3

输入

5 1000000000
abc
acde
cefg
abcfh
dghi

输出

346462871

说明/提示

限制条件

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

样例解释 1

可以输入的字符串有 aa、ab、ac、ba、bb、ca、cc，共 $7$ 种。

样例解释 3

请输出答案对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译