3684. 灌水社区

小CLZ的温馨提示：在题目描述中有形式化的题面，你可以选择跳过题目背景。同时请仔细将本题的除题目背景以外的所有内容进行完整阅读后再进行做题。但是题目背景里有一点的帮助理解的信息就是了。 

【题目背景】

2022年统一省选 D1T3 的出题人小 CLZ 是一个喜欢出题的选手，不过，与其说小 CLZ 喜欢 OI，不如说小 CLZ喜欢的是出完题后接受大家的夸赞（把网络流和字符串结合起来的思想毕竟一般人难以想出）。近日，著名OJ——CS:GO——添加了灌水社区这一趣味功能，小 CLZ 当然要到这里冲浪一番，于是他发了这个帖子：

CLZ: 萌新求助，今年省选 D1T3 出的怎么样

BS：CLZ楼下

WQ: BS楼下

ZRQ: CLZ楼上

CLZ: 能不能别魔怔了，大家正经回答问题

RSR: CLZ楼下

RSR: RSR楼下

CLZ：

CLZ: CLZ楼上

CLZ: CLZ楼下

CLZ: CLZ楼上

CLZ: CLZ楼下

……

虽然自己因为没有人回答他的“学术”问题被激怒了，但 CS:GO 人有趣的发言方式让 CLZ 乐呵了许久，这说明人类的悲欢并不想通。不过当小 CLZ 刷新界面想要往下浏览大家的回复时，却发现灌水社区的管理员因为这个帖子过于学术把它删除了。

为了恢复这个有趣的帖子，小 CLZ 对着网页缓存倒腾了许久，还原出了这个帖子的每条消息。然而因为神秘原因，消息的顺序被打乱了，还混入了并不属于这个帖子的信息，且缓存中没有每条消息发送的时间，因而小 I 没有办法还原原始帖子中消息的顺序。

秉承“遇到困难出题让选手睡大觉”精神的小 CLZ 决定随便给帖子里的消息排个顺序，不过深受“XXX楼上”“XXX楼下”这种发言形式吸引的小 CLZ 还是希望重排之后有至少 $n$ 条符合实际情况的信息。然而小 CLZ 是一个只会水社区和让选手不会做题的 OI 出题人，所以小 CLZ 求助于你。

当然了，小 CLZ 知道直接将帖子中的原始信息丢给你对你来说是不方便的，所以他对信息进行了一些规范化处理，详见题目描述中的形式化题意。同时由于学术社区的特殊规定，帖子中的消息满足一定特殊限制，详见题目描述最后。

【题目描述】

以下涉及的所有字符串判等操作都对大小写敏感，例如 loushang、Loushang、LOUSHANG是互不相同的字符串。但是！本题目保证不会出现loushang、Loushang、LOUSHANG这种离谱的字符串判等！

小 CLZ 正在整理学术社区中的一个帖子。帖子中共有 $p$ 个网友发过消息，他们的网名分别为$n_1,n_2,\cdots,n_N$。帖子中总共有 $m$ 条消息，对于第 $i$ 条消息，我们用两个字符串和一个布尔数

$s_{i,1},s_{i,2},s_{i,3}$ 构成的三元组描述它，其中 $s_{i,1}$ 表示这条消息发出者的网名，而 $s_{i,2}$ 和 $s_{i,3}$ 描述这条消息的内容。

对于第 $i$ 条消息，我们通过如下方式定义其属于楼下型消息、楼上型消息中的哪一种：

若布尔数 $s_{i,3}$ 为 $0$ ，且 $s_{i,2}$ 恰好与给出的某个网名相同(注意 $s_{i,2}=s_{i,1}$ 是允许的)，则称这条消息是楼下型消息，$s_{i,2}$ 对应这条消息提到的网友；

若布尔数 $s_{i,3}$ 为 $1$ ，且 $s_{i,2}$ 恰好与给出的某个网名相同(注意 $s_{i,2}=s_{i,1}$ 是允许的)，则称这条消息是楼上型消息，$s_{i,2}$ 对应这条消息提到的网友；

定义一个对所有消息的重排方案为一个 $1$ 到 $m$ 的排列 $a_1,a_2,a_3,\cdots,a_M$，表示第一条消息是 $(s_{a_1,1},s_{a_1,2}, s_{a_1,3})$，第二条消息是 $(s_{a_2,1},s_{a_2,2}, s_{a_2,3})$，依此类推。

对于一个重排方案 $a_1,a_2,a_3,\cdots,a_m$ 中的第 $i(1\leq i\leq M)$ 条消息 $(s_{a_i,1},s_{a_i,2}, s_{a_i,3})$，如下定义其是否是符合实际情况的：

若这条消息是楼下型消息，则这条消息是符合实际情况的当且仅当 $i\neq 1$且$s_{a_{i-1}, 1}=s_{a_i,2}$，即上一条消息存在且它的发出者与这条消息提到的网友一致。

若这条消息是楼上型消息，则这条消息是符合实际情况的当且仅当 $i\neq M$且$s_{a_{i+1}, 1}=s_{a_i,2}$，即下一条消息存在且它的发出者与这条消息提到的网友一致。

在以上定义下，小 CLZ 希望知道在信息数量大于等于 $n$ 的所有的重排方案中任意取一个符合实际情况的消息数量大于等于 $n$ 的方案概率。

【输入格式】

第一行两个整数 $n, m,p$ 分别表示重排方案最少信息数，帖子的消息数量以及发言的网友数。

接下来 $1$ 行 $p$ 个字符串 $P$ 表示在帖子中发过消息的 $p$ 个网友的网名。保证每个测试数据中输入的 $p$ 个网友的网名两两不同。

接下来 $m$ 行每行三个字符串 $s_1, s_2, s_3$ 描述一条消息，相邻的字符串之间用一个空格分隔，其中 $s_1$ 一定与输入中某个网友的网名相等。

输入的所有字符串仅由大小写英文字母、下划线(_)、英文问号(?)、英文感叹号(!)和英文句号(.)构成，且长度不超过 12。

可能存在多条消息内容完全一致，此时应将他们视为多条消息。

保证所有输入均合法，也就是每条信息中 $s_1,s_2$ 均为网友名， $s_3$为 $0$ 或 $1$。(OIERS: 终于不用做离谱的字符串判等这种无脑增加代码长度的东西了) 

【输出格式】

输出仅一行两个整数。

如果答案的最简分数表示为 $\frac{x}{y}(x \ge 0,y \ge 1,\gcd(x,y)=1)$，你需要输出两个数 $x$ $y$  。

【样例输入】

2 4 3
C Y X
X Y 1
C X 1
C C 0
Y X 0

【样例输出】

11 60

【样例说明】

为了选手们的健康，身为著名出题人的小 CLZ 怎么会不给大家详细的样例说明呢？

当重排方案长度为 $2$ 时:

共有 $12$ 种重排方案，其中有 $1$ 个符合题意。

当重排方案长度为 $3$ 时:

共有 $24$ 种重排方案，其中有 $4$ 个符合题意。

当重排方案长为 $4$ 时:

共有 $24$ 种重排方案，其中有 $6$ 个符合题意。

由以上可知，共有 $60$ 种可能的重排方案，其中符合题意的有 $11$ 种，故 $x = 11 , y = 60$ 。

【数据规模与约定】

对于 $10$% 的数据， $n = 1$ 。

对于 $100$% 的数据，$1 <= n <=m <=11 , p <=50$。

【来源】

出题人: seium