Description

经过多年的研究，Google Labs 的科学家们发现了一种来自遥远星球的外星语言。这种外星语言非常独特，每个单词恰好由 $L$ 个小写字母组成。此外，这种语言中恰好有 $D$ 个单词。

在建立了该外星语言所有单词的字典后，科学家们的下一个重大突破是发现，外星人在过去十年间一直在向地球发送信息。不幸的是，由于两颗星球之间的距离遥远，这些信号在传输过程中被削弱，导致部分单词可能被误解。为了帮助科学家们解读这些信息，他们请你设计一个算法，能够判断给定模式下可能的解释数量。

一个模式恰好由 $L$ 个符号组成。每个符号要么是一个小写字母（科学家们非常确定这就是那个字母），要么是由圆括号括起来的一组互不相同的小写字母。例如：(ab)d(dc) 表示第一个字母可以是 a 或 b，第二个字母一定是 d，第三个字母可以是 d 或 c。因此，模式 (ab)d(dc) 可能代表以下 4 种情况之一：add、adc、bdd、bdc。

Input Format

输入的第一行包含 3 个整数 $L$、$D$ 和 $N$，以空格分隔。接下来的 $D$ 行，每行一个长度为 $L$ 的单词，表示该外星语言已知的单词。所有已知单词保证互不相同。接下来有 $N$ 个测试用例，每个测试用例一行，均为如上描述的模式。

Output Format

对于每个测试用例，输出

Case #$X$: $K$

其中 $X$ 表示测试用例编号（从 1 开始），$K$ 表示有多少个外星语言中的单词与该模式匹配。

3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

Hint

限制条件

小数据集（10 分）

• $1 \leq L \leq 10$
• $1 \leq D \leq 25$
• $1 \leq N \leq 10$

大数据集（23 分）

• $1 \leq L \leq 15$
• $1 \leq D \leq 5000$
• $1 \leq N \leq 500$

翻译由 ChatGPT-4.1 完成。