3057 - Bill的挑战
时间限制 : 1 秒
内存限制 : 128 MB
这次,比赛规则是这样的:
给出 N 个长度相同的字符串(由小写英文字母和 ?
组成),S_1,S_2,\dots,S_N,求与这 N 个串中的刚好 K 个串匹配的字符串 T 的个数,答案对 1000003 取模。
若字符串 S_x(1\le x\le N) 和 T 匹配,满足以下条件:
- |S_x|=|T|。(即两个字符串的长度相同)
- 对于任意的 1\le i\le|S_x|,满足 S_x[i]= \texttt{?} 或者 S_x[i]=T[i]。
其中 T 只包含小写英文字母。
输入
第一行一个整数 T,表示数据组数。
对于每组数据,第一行两个整数,N 和 K。
接下来 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 5,1\le N \le15,1\le|S_i|\le50。 保证单组测试点内的所有的字符串长度都相同。
来源
山东省选