3057 - Bill的挑战

通过次数

1

提交次数

1

时间限制 : 1 秒
内存限制 : 128 MB

这次,比赛规则是这样的:

给出 N 个长度相同的字符串(由小写英文字母和 ? 组成),S_1,S_2,\dots,S_N,求与这 N 个串中的刚好 K 个串匹配的字符串 T 的个数,答案对 1000003 取模。

若字符串 S_x(1\le x\le N)T 匹配,满足以下条件:

  1. |S_x|=|T|。(即两个字符串的长度相同)
  2. 对于任意的 1\le i\le|S_x|,满足 S_x[i]= \texttt{?} 或者 S_x[i]=T[i]

其中 T 只包含小写英文字母。

输入

第一行一个整数 T,表示数据组数。

对于每组数据,第一行两个整数,NK

接下来 N 行,每行一个字符串 S_i

输出

每组数据输出一行一个整数,表示答案。

样例

输入

5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??

输出

914852
0
0
871234
67018

提示

  • 对于 100\% 的数据,1\le T\le 51\le N \le151\le|S_i|\le50。 保证单组测试点内的所有的字符串长度都相同。

来源

山东省选