2077. 狗剩想吃蛋糕

单点时限: 40.0 sec

内存限制: 256 MB

jysgs 饿了,qwynick 手里有个大蛋糕,但是 qwynick 不会这么轻易给 jysgs 吃,qwynick 要考考 jysgs。qwynick 拿出 n 张卡片,每张卡片上有都有一个长度一样的由小写字母和 ‘?’ 组成的字符串。问题出来了,有多少个由小写字母组成的字符串与 n 个字符串中的 k 个匹配,而与其他 n-k 个不匹配?qwynick 规定两个字符串匹配,当且仅当他们相应位置的字符一样或者某一个串在该位置为 ‘?’。

输入格式

多组测试数据,由空行隔开。每组测试数据的第一行是一个整数 n(1<=n<=15),接下来 n 行每行都有一个长度不超过 50 且只含小写字母和 ‘?’ 的字符串,字符串输入结束后输入一个整数 k(1<=k<=n)。

输出格式

记只和 n 个字符串中 k 个匹配的只含小写字母的字符串的个数为 S, 输出 S%1000003 的结果。

样例

Input
1
?
1
3
a
b
c
1
2
a?
?b
2
1
?????
1
Output
26
3
1
881343
Hint:
Case1:"a"-"z"都符合
Case2:"a","b","c"
Case3:"ab"
Case4:26^5%1000003

1 人解决,4 人已尝试。

1 份提交通过,共有 9 份提交。

9.9 EMB 奖励。

创建: 13 年,10 月前.

修改: 4 年,4 月前.

最后提交: 11 年,1 月前.

来源: N/A

题目标签