OI题库

问题描述：
Sheng bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借
优秀的程序与他打成了平局，这导致Sheng bill极度的不满。于是他再次挑战你。这次你可不
能输！
这次，比赛规则是这样的：
给N个长度相同的字符串（由小写英文字母和′
?′
组成），S1, S2, . . . , SN，求与这N个串中
的刚好K个串匹配的字符串T的个数（答案模1000003）。
若字符串Sx（1 ≤ x ≤ N）和T匹配，满足以下条件：
1. Sx.length = T.length。
2. 对于任意的1 ≤ i ≤ Sx.length，满足Sx[i] =′
?′
或者Sx[i] = T[i]。
其中T只包含小写英文字母。
输入格式：
本题包含多组数据。
第一行：一个整数T，表示数据的个数。
对于每组数据：
第一行：两个整数，N和K（含义如题目表述）。
接下来N行：每行一个字符串。
输出格式：
对于每组数据，输出方案数目（共T行）。
样例输入：
1
2 1
a?
?b
样例输出：
50
数据范围：
对于30%的数据，T ≤ 5，N ≤ 5，字符串长度≤ 20；
对于70%的数据，T ≤ 5，N ≤ 13，字符串长度≤ 30；
对于100%的数据，T ≤ 5，N ≤ 15，字符串长度≤ 50。