像往常一样，$N$ 个机器人正在玩狼人杀游戏，机器人的编号为 $1$ 到 $N$。这些机器人中恰好有 $W$ 个是狼人，其余的是平民。虽然狼人杀游戏包含多个环节，但我们只关注游戏中的一个发言阶段。

机器人会指控其他机器人是狼人，或者通过为其清白担保来保护其他机器人。

狼人知道彼此的身份，并且：

• 狼人绝不会指控另一个狼人；
• 被狼人保护的任何机器人也一定是狼人。

平民可以指控或保护任意类型的机器人。

一些额外的限制使我们的任务变得简单了一些：

• 没有机器人会同时被指控和被保护。
• 没有机器人会被指控或保护超过一次。
• 如果机器人 $A$ 指控或保护机器人 $B$，则必有 $A < B$。

给你 $N$ 个机器人之间的所有指控和保护关系，其中恰好有 $W$ 个狼人。一种角色分配方案是指将每个机器人分别指定为狼人或平民。你的目标是计算有多少种角色分配方案满足上述所有约束条件。

输入格式

第一行包含三个整数（每个数之间用一个空格隔开）：

• $N$ ($1 \le N \le 200$)，表示机器人的数量；
• $W$ ($0 \le W \le N$)，表示狼人的数量；
• $M$ ($0 \le M < N$)，表示指控和保护关系的数量。

接下来的 $M$ 行给出指控和保护关系。每行将是以下两种形式之一：

• A a b 表示机器人 $a$ 指控机器人 $b$ 是狼人；
• D a b 表示机器人 $a$ 保护机器人 $b$。

输出格式

输出与给定信息一致的角色分配方案数。由于这个数量可能非常大，你必须输出该答案模 $10^9 + 7$ 的结果。

数据范围

对于 $20\%$ 的测试数据，满足 $N \le 20$。

样例

输入样例 1

2 1 1
D 1 2

输出样例 1

1

说明 1

如果机器人 1 是狼人，那么机器人 2 也必须是狼人，这会导致狼人数量过多（因为 $W=1$）！因此唯一的可能性是机器人 2 是唯一的狼人。

输入样例 2

2 1 0

输出样例 2

2

说明 2

在没有任何信息的情况下，机器人 1 或机器人 2 都有可能是狼人。

输入样例 3

3 2 2
A 1 2
D 1 3

输出样例 3

2

说明 3

要么机器人 1 是狼人（这意味着机器人 2 是平民，且机器人 3 也是狼人），要么机器人 1 是平民（这允许机器人 2 和机器人 3 都是狼人）。