#PQJ149x4182. QOJ 149_4182

    ID: 2621 传统题 500ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2009字符串组合数学

QOJ 149_4182

Time Limit: 1s → 0.5s

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

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

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

若字符串 𝑆 𝑥 ( 1 ≤ 𝑥 ≤ 𝑁 )和 𝑇 匹配,满足以下条件:

| 𝑆 𝑥 |

| 𝑇 | 对于任意的 1 ≤ 𝑖 ≤ | 𝑆 𝑥 | ,满足 𝑆 𝑥 [ 𝑖 ]

? 或者 𝑆 𝑥 [ 𝑖 ]

𝑇 [ 𝑖 ] 。

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

输入格式

本题包含多组数据。

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

对于每组数据:

第一行:两个整数, 𝑁 和 𝐾 (含义如题目表述)。 接下来 𝑁 行:每行一个字符串。 输出格式

输出一行一个整数,表示答案模 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 % 的数据, 𝑁 ≤ 5 。

对于 50 % 的数据, 𝑁 ≤ 10 。

对于 70 % 的数据, 𝑁 ≤ 13 。

对于 100 % 的数据, 𝑇 ≤ 5 , 𝐾 ≤ 𝑁 ≤ 15 ,字符串长度 𝐿 ≤ 50 。