← 返回题目列表

AtCoder · abc246_f

I. 打字机

中文机器翻译题面 查看原题

分数: 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.