3317. 子串

单点时限: 2.0 sec

内存限制: 256 MB

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

现在我们定义 :构造一个由 E, O, J 组成的字符串,使得在给定的 个模板串中,恰好有 个在这个字符串中出现过。我们共可以构造 个这样的字符串。那么,学过小学奥数的我们都知道,

试求 。结果可能很大,模

输入格式

第一行是两个整数

接下来 行,每行一个模板串。保证各不相同,都是由 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 的数目 ,出现 EOJ 。所以答案为

样例 2:,答案为

1 人解决,1 人已尝试。

1 份提交通过,共有 1 份提交。

8.9 EMB 奖励。

创建: 2 年,3 月前.

修改: 2 年,2 月前.

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

来源: N/A

题目标签