和往常一样，N 个机器人在玩狼人游戏，机器人从 1 到 N 编号。W 个机器人扮演狼人，剩下的扮演市民。虽然狼人游戏包括不同的角度，但我们将只着眼于其中一个角度。

机器人指控其他人是狼人并且防止其他机器人无辜地指控它。

狼人知道其他人的角色以及：

• 一个狼人从不指控其他狼人；

• 任何狼人机器人保护的都是其他狼人机器人。

市民可能会指控或保护任何类型的机器人。

其他的一些限制使得题目更简单：

• 没有机器人又被指控又被保护；

• 没有机器人被指控或保护一次以上；

• 如果有一个编号为 A 机器人指控或保护编号为 B 的机器人，那么我们保证A。

你将知道 N 个机器人间的所有指控和保护关系，并且知道狼人数为 W。每个机器人所扮演的角色要么是狼人要么是市民。你的目标是计算出符合上述限制的角色安排方案数。

第一行三个数 N,W,M，分别表示机器人数、狼人数、指控和保护关系数。

接下来 M 行每行描述一个关系，接下来每行都是以下两个形式之一：

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

输出满足以上条件的角色安排方案数量。可想而知，结果可能非常大，所以需要对 10^9+7 取模。

样例解释 1

如果机器人 1 是狼人，机器人 2 也必须是，那么狼人就太多了！唯一的可能是机器人 2 是唯一的狼人。

样例输出 2

没有额外的保护或指控信息的话，机器人 1 和机器人 2 都可能是狼人。

样例解释 3

如果机器人 1 是狼人，机器人 2 将是市民，机器人 3 也是狼人；或者机器人 1 是市民，那么机器人 2 和 3 将是狼人。

对于 20\% 的数据，1\le N\le 20；

对于 100\% 的数据，1\le N\le 200, 0\le W\le N, 0\le M。

CCO