P16590 [GKS 2016 #D] Codejamon Cipher

**CodejamOn** 怪物使用加密的消息进行交流。其工作原理如下： 每种怪物都有自己独特的词汇表：一个包含 $V$ 个不同单词的列表，单词仅由小写英文字母组成。当怪物说话时，它首先使用词汇表中的单词组成一个句子；同一个单词可以在句子中出现多次。然后，它将句子转换为加密字符串，方法如下： 1. 将句子中的每个单词随机打乱。 2. 删除所有空格。 理解怪物能为你带来巨大优势，因此你正在构建一个工具来完成这项任务。作为第一步，你需要能够根据一个加密字符串，确定有多少种可能的原始句子能够生成该加密字符串。例如，如果怪物的词汇表是 `["this", "is", "a", "monster", "retsnom"]`，并且它说出了加密字符串 `"ishtsiarestmon"`，则有四种可能的原始句子： * "is this a monster" * "is this a retsnom" * "this is a monster" * "this is a retsnom" 你拥有来自同一怪物的 $S$ 个加密字符串。对于每个字符串，你能计算出可能的原始句子的数量吗？ **重要**：由于输出可能非常大，我们只要求你输出结果除以素数 $10^9 + 7$（$1000000007$）的余数。

输入的第一行给出测试用例的数量 $T$；接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $V$ 和 $S$，分别表示怪物的词汇表大小和加密字符串的数量。随后 $V$ 行，每行包含一个由小写英文字母组成的字符串，表示怪物词汇表中的一个单词。最后 $S$ 行，每行包含一个仅由小写英文字母组成的字符串，表示一个加密句子。保证所有加密句子都是有效的，即每个句子至少有一个可能的原始句子。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个空格分隔的列表，包含 $S$ 个整数：按照输入顺序，每个加密句子对应的答案（模 $10^9 + 7$）。

### 限制条件 $1 \le T \le 100$。 $1 \le S \le 5$。 **小数据集（测试集 1 – 可见）** $1 \le \text{词汇表中每个单词的长度} \le 5$。 $1 \le \text{加密字符串的长度} \le 50$。 $5 \le V \le 10$。 **大数据集（测试集 2 – 隐藏）** $1 \le \text{词汇表中每个单词的长度} \le 20$。 $2000 \le \text{加密字符串的长度} \le 4000$。 $200 \le V \le 400$。 翻译由 DeepSeek V4 Pro 完成