[SDOI2009]Bill的挑战

题目描述

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

914852

0

0

871234

67018

说明

### 数据规模与约定 - 对于 $30\%$ 的数据,$N\le5$,$|S_i|\le20$; - 对于 $70\%$ 的数据,$N\le13$,$|S_i|\le30$; - 对于 $100\%$ 的数据,$1\le T\le 5$,$1\le N \le15$,$1\le|S_i|\le50$。