题目描述

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$）。

2
5 1
this
is
a
good
day
sithsiaodogyad
5 3
pt
ybsb
xnydt
qtpb
kw
xnydttbpqtpqb
yxdtntpbsby
ptptxytdnsbybpt

Case #1: 2
Case #2: 1 1 1

提示

限制条件

$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 完成