QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 128 MB Total points: 100
统计

Time Limit: 1s → 0.5s

Sheng_bill 不仅有惊人的心算能力,还可以轻松地完成各种统计:在昨天的比赛中,你凭借优秀的程序与他打成了平局,这导致 Sheng_bill 极度的不满,于是他再次挑战你。这次你可不能输!

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

给 $N$ 个长度相同的字符串(由小写英文字母和 ? 组成),求与这 $N$ 个串中的刚好 $K$ 个串匹配的字符串 $T$ 的个数(答案模 $1\,000\,003$)。

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

  1. $|S_x| = |T|$
  2. 对于任意的 $1 \leq i \leq |S_x|$,满足 $S_x[i] =\,?$ 或者 $S_x[i] = T[i]$。

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

输入格式

本题包含多组数据。

第一行:一个整数 $T$,表示数据的个数。

对于每组数据:

  • 第一行:两个整数,$N$ 和 $K$(含义如题目表述)。
  • 接下来 $N$ 行:每行一个字符串。

输出格式

输出一行一个整数,表示答案模 $1\,000\,003$

样例数据

样例输入

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

样例输出

914852
0
0
871234
67018

子任务

对于 $30\%$ 的数据,$N \leq 5$。

对于 $50\%$ 的数据,$N \leq 10$。

对于 $70\%$ 的数据,$N \leq 13$。

对于 $100\%$ 的数据,$T \leq 5$,$K \leq N \leq 15$,字符串长度 $L \leq 50$。