P83057

Bill的挑战

难度 7 级 初三 动态规划入门 状态压缩
讨论 统计 2通过 2提交 100%通过率 旧版界面
时间限制 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,表示数据组数。

对于每组数据,第一行两个整数,N 和 K。

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

输出

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

样例

样例 1
输入
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。 保证单组测试点内的所有的字符串长度都相同。

来源

山东省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交