分数: 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
输出
打印答案。
示例输入 1
2 2 ab ac
示例输出 1
7
我们可以输入七个字符串: aa, ab, ac, ba, bb, ca, cc.
示例输入 2
4 3 abcdefg hijklmnop qrstuv wxyz
示例输出 2
1352
示例输入 3
5 1000000000 abc acde cefg abcfh dghi
示例输出 3
346462871
请务必打印答案模数 998244353.