#P2167. [SDOI2009] Bill的挑战

    ID: 1185 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2009各省省选山东枚举暴力状态压缩状压

[SDOI2009] Bill的挑战

题目描述

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

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

给出 NN 个长度相同的字符串(由小写英文字母和 ? 组成),S1,S2,,SNS_1,S_2,\dots,S_N,求与这 NN 个串中的刚好 KK 个串匹配的字符串 TT 的个数,答案对 10000031000003 取模。

若字符串 Sx(1xN)S_x(1\le x\le N)TT 匹配,满足以下条件:

  1. Sx=T|S_x|=|T|
  2. 对于任意的 1iSx1\le i\le|S_x|,满足 Sx[i]=?S_x[i]= \texttt{?} 或者 Sx[i]=T[i]S_x[i]=T[i]

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

输入格式

本题包含多组数据

第一行一个整数 TT,表示数据组数。

对于每组数据,第一行两个整数,NNKK

接下来 NN 行,每行一个字符串 SiS_i

输出格式

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

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%30\% 的数据,N5N\le5Si20|S_i|\le20
  • 对于 70%70\% 的数据,N13N\le13Si30|S_i|\le30
  • 对于 100%100\% 的数据,1T51\le T\le 51N151\le N \le151Si501\le|S_i|\le50