时间限制： 1.0 秒

空间限制： 512 MB

题目描述

我们有一副纸牌，它由 $n$ 张牌组成，其中每张牌上标有一个数字（0 到 9）和一个大写字母（A 到 Z），例如 2C、1F。

我们如下定义一个字符串与一张牌之间的匹配关系：

• 字符串 ?? 与任何一张牌都匹配。
• 第一位为 ? 而第二位为字母的字符串，与任何一张标有该字母的牌匹配。例如，字符串 ?C 与任何标有 C 的牌匹配。
• 第一位为数字而第二位为字母的字符串，仅与内容完全一致的牌匹配。例如，字符串 0C 与内容为 0C 的牌匹配。
• 不会出现第一位为数字而第二位为 ? 的字符串。

我们称 $m$ 个字符串 $S_1, \dots, S_m$ 与 $m$ 张牌 $C_1, \dots, C_m$ 是匹配的，当且仅当：存在集合 $\{1, \dots, m\}$ 上的一一映射 $\sigma$，使得对于任意 $1 \le i \le m$，$S_i$ 与 $C_{\sigma(i)}$ 匹配。

例如，对于 ?? 和 ?C 这两个字符串，可以匹配内容为 1C 和 2C 的牌，因为字符串 ?? 与内容为 2C 的牌匹配且字符串 ?C 与内容为 1C 的牌匹配，而 ?? 和 ?C 这两个字符串不能匹配内容为 1S 和 1P 的牌。

现在，给定 $m$ 个字符串，你需要求解：如果在 $n$ 张牌中（无放回地）随机选取 $m$ 张，有多大概率与这些字符串匹配？

输入格式

从标准输入读入数据。

本题包含多组测试数据。

第一行输入该文件的数据个数 $T$。

对于每组测试数据：

共计三行，其中：

• 第一行输入两个正整数 $n$ 和 $m$；
• 第二行输入以空格分隔的 $n$ 个字符串，表示每张纸牌的内容（每个字符串第一位为数字，第二位为大写字母）；
• 第三行输入以空格分隔的 $m$ 个字符串，表示每个需要匹配的字符串（每个字符串第一位为数字，第二位为大写字母；或第一位为 ?，第二位为大写字母；或为 ??）。

输出格式

输出到标准输出。

对于每组测试数据：

输出一行，表示所求的概率。概率需要以最简分数 $u/v$ 的形式输出，其中 $0 \leq u \leq v$ 且 $u, v$ 为互质的整数。特殊地，对于 $0$ 请输出 0/1，对于 $1$ 请输出 1/1。

15
6 1
0C 0S 0P 1C 1S 1P
1S
6 1
0C 0S 0P 1C 1S 1P
?C
6 2
0C 0S 0P 1C 1S 1P
?C ?C
6 2
0C 0S 0P 1C 1S 1P
?C ?S
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?S ?P
6 4
0C 0S 0P 1C 1S 1P
0C ?C ?S ?P
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?S ??
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?? ??
6 4
0C 0S 0P 1C 1S 1P
?A ?? ?? ??
6 4
0C 0S 0P 1C 1S 1P
0C 0C ?S ?P
30 8
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
0C ?C ?C ?C 1S ?S 2P ?P
40 2
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
?C 1C
40 2
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
?C 1S
40 16
0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P
0C 0C 1C 2C ?C ?C ?C ?C 3S 4S ?S ?S 5P 6P ?P ?P
60 30
1A 1B 1C 1D 1E 1F 1G 1H 1I 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 0A 1A 2A 3A 4A 5A 6A 7A 8A 9A 1S 3S 5S 7S 9S 0U 2U 4U 6U 8U 2Z 3Z 5Z 7Z 1C 1C 1C 1C 1C 1C 1C 1C 1S 1P
1C 1C 1S 1P 2A 0A 1A 9A ?S ?U ?Z ?H ?O ?U ?? ?? ?? ?? ?? ?? ?S ?S ?S ?U ?U ?U ?Z ?Z ?C ?C

1/6
1/3
1/15
4/15
4/15
4/15
1/3
2/5
0/1
0/1
252/216775
37/780
1/39
167384/2417388525
50442363273/29566145391215356

子任务

对于所有的数据，$1 \leq m \leq n \leq 60$；$T \leq 1000$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（11 分）：$m=1$；
• 子任务 2（23 分）：$m=n$；
• 子任务 3（27 分）：$n=30$ 且所有的牌为 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P；
• 子任务 4（22 分）：$n=40$ 且所有的牌为 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P；
• 子任务 5（17 分）：无特殊限制。

提示

对于分数 $a/b$，设 $g=\gcd(a,b)$，那么其最简分数形式为 $(a/g)/(b/g)$。

$\gcd(a,b)$ 可以这样计算：如果 $a=0$ 则答案为 $b$，否则为 $\gcd(b \bmod a, a)$（需要递归计算）。