#PQJ149x4182. QOJ 149_4182
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 。