#P2167. [SDOI2009] Bill的挑战
[SDOI2009] Bill的挑战
题目描述
Sheng_bill 不仅有惊人的心算能力,还可以轻松地完成各种统计。在昨天的比赛中,你凭借优秀的程序与他打成了平局,这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。
这次,比赛规则是这样的:
给出 个长度相同的字符串(由小写英文字母和 ?
组成),,求与这 个串中的刚好 个串匹配的字符串 的个数,答案对 取模。
若字符串 和 匹配,满足以下条件:
- 。
- 对于任意的 ,满足 或者 。
其中 只包含小写英文字母。
输入格式
本题包含多组数据。
第一行一个整数 ,表示数据组数。
对于每组数据,第一行两个整数, 和 。
接下来 行,每行一个字符串 。
输出格式
每组数据输出一行一个整数,表示答案。
5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??
914852
0
0
871234
67018
提示
数据规模与约定
- 对于 的数据,,;
- 对于 的数据,,;
- 对于 的数据,,,。