3317. 子串

单点时限: 2.0 sec

内存限制: 256 MB

长度为 $L$ 的,由 E, O, J 组成的字符串,众所周知,有 $3^L$ 个。

现在我们定义 $d(k)$:构造一个由 E, O, J 组成的字符串,使得在给定的 $n$ 个模板串中,恰好有 $k$ 个在这个字符串中出现过。我们共可以构造 $d(k)$ 个这样的字符串。那么,学过小学奥数的我们都知道,$\displaystyle \sum_{k=0}^n d(k) = 3^L$。

试求 $\displaystyle \sum_{k=0}^n (k+1)^2 d(k)$。结果可能很大,模 $998~244~353$。

输入格式

第一行是两个整数 $n, L$。

接下来 $n$ 行,每行一个模板串。保证各不相同,都是由 E, O, J 组成的。

输出格式

输出一行,一个整数。

样例

Input
1 3
EOJ
Output
30
Input
2 5
EOJ
JOE
Output
409
Input
3 5
E
O
J
Output
3222
Input
3 100
E
O
J
Output
703923570

提示

样例 1:长度为 3 且不出现 EOJ 的数目 $d(0) = 26$,出现 EOJ $d(1) = 1$。所以答案为 $30$。

样例 2:$d(0)=191, d(1)=50, d(2)=2$,答案为 $409$。

2 人解决,2 人已尝试。

2 份提交通过,共有 37 份提交。

8.6 EMB 奖励。

创建: 7 年,1 月前.

修改: 7 年,1 月前.

最后提交: 3 年,10 月前.

来源: N/A

题目标签