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

输入 #1

2 2
ab
ac

输出 #1

7

输入输出样例 #2

输入 #2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

输出 #2

1352

输入输出样例 #3

输入 #3

5 1000000000
abc
acde
cefg
abcfh
dghi

输出 #3

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 翻译