P17392 [ICPC 2018 Shenyang R] Sockpuppets

Pheatr 有很多账户，用于参加在线编程竞赛，比如 TopForces 上的比赛。 有时当 Pheatr 参加 TopForces 的比赛但无法直接获得好成绩时，他会利用一些用于作弊的额外账户（即马甲）来获得更高的分数：起初，他构造一些能通过预系统测试的错误代码，并通过马甲提交它们。之后，他立刻用自己的主账户去挑战这些马甲，因为一次成功的挑战能为他多带来 $100$ 分。 事实上，Pheatr 并不是唯一在比赛中作弊的人。很多参赛者在在线编程竞赛中都使用相同的策略。众所周知，每个人都只有一个主账户。如果一个人的作弊行为被揭露，其主账户将被永久封禁。为了防止这一不光彩的事实暴露，每名参赛者最多只会注册两个马甲。尽管冒着巨大的风险，当他们注册马甲时，这些参赛者总是遵循同一条规则：属于一名参赛者的马甲的用户名必须是该参赛者主账户用户名的前缀，否则主账户的用户名必须是马甲用户名的前缀。 最近，TopForces 的一次泄密提供了一份已确认的、使用过马甲作弊的作弊者名单，其中包含他们主账户的用户名。此外，TopForces 还公布了一份可疑账户列表，暗示其中某些可能是马甲。为了区分这些可疑账户并指出它们的主人，Pheatr 打算根据已公布的信息描绘出所有的可能情况。当然，必须注意，有些可疑账户可能是被冤枉的，并不属于任何已知的作弊者。 在认可了你出色的编程能力之后，Pheatr 请你统计出在已确认的作弊者和可疑账户之间声明归属关系的所有不同可能情况的总数。如果两种可能情况中，每个可疑账户都同时被冤枉，或者都归属于同一个作弊者，则认为这两种可能情况相同。由于答案可能非常大，你只需要输出答案对 $(10^9 + 7)$ 取模的结果。

输入包含多个测试用例，第一行包含一个正整数 $T$，表示测试用例的个数，最多为 $100$。 对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，分别表示泄密中已知作弊者的数量和 TopForces 提供的可疑账户的数量，其中 $1 \le n, m \le 1000$。 接下来的 $n$ 行，每行包含一个非空字符串 $s$，全部由小写字母构成，表示一个已知作弊者的主账户用户名，$s$ 的长度不超过 $10$。 再接下来的 $m$ 行，每行包含一个非空字符串 $t$，全部由小写字母构成，表示一个可疑账户的用户名，$t$ 的长度不超过 $10$。 我们保证在同一个测试用例中出现的所有用户名互不相同。

对于每个测试用例，输出一行 `Case #x: y`（不含引号），其中 $x$ 是测试用例的编号，从 $1$ 开始，$y$ 是对该测试用例答案取模 $(10^9 + 7)$ 后的结果。

在第一个样例中，马甲 $\texttt{aa}$ 和 $\texttt{aaa}$ 都可以属于 $\texttt{a}$ 的主人。 在第二个样例中，马甲 $\texttt{ab}$ 不能属于 $\texttt{aa}$ 的主人，而 $\texttt{a}$ 可以。 在第三个样例中，每个马甲都可以属于 TopForces 泄露名单中的任意一个人。 翻译由 DeepSeek V4 Pro 完成