A6611 | $「SDOI2009」Bill 的挑战$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。 这次，比赛规则是这样的： 给出 $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??

输出 #1

C++ 编辑器

输入

输出