[CCO2014] 狼人游戏
题目描述
**本题译自 [CCO 2014](https://cemc.math.uwaterloo.ca/contests/computing/2014/index.html) Day1 T3「[Werewolf](https://cemc.math.uwaterloo.ca/contests/computing/2014/Stage%202/day1.pdf)」**
和往常一样,$N$ 个机器人在玩狼人游戏,机器人从 $1$ 到 $N$ 编号。$W$ 个机器人扮演狼人,剩下的扮演市民。虽然狼人游戏包括不同的角度,但我们将只着眼于其中一个角度。
机器人指控其他人是狼人并且防止其他机器人无辜地指控它。
狼人知道其他人的角色以及:
- 一个狼人从不指控其他狼人;
- 任何狼人机器人保护的都是其他狼人机器人。
市民可能会指控或保护任何类型的机器人。
其他的一些限制使得题目更简单:
- 没有机器人又被指控又被保护;
- 没有机器人被指控或保护一次以上;
- 如果有一个编号为 $A$ 机器人指控或保护编号为 $B$ 的机器人,那么我们保证$A<B$。
你将知道 $N$ 个机器人间的所有指控和保护关系,并且知道狼人数为 $W$。每个机器人所扮演的角色要么是狼人要么是市民。你的目标是计算出符合上述限制的角色安排方案数。
输入输出格式
输入格式
第一行三个数 $N,W,M$,分别表示机器人数、狼人数、指控和保护关系数。
接下来 $M$ 行每行描述一个关系,接下来每行都是以下两个形式之一:
- `A a b`,表示机器人 $a$ 指控机器人 $b$ 是狼人。
- `D a b`,表示机器人 $a$ 保护机器人 $b$。
输出格式
输出满足以上条件的角色安排方案数量。可想而知,结果可能非常大,所以需要对 $10^9+7$ 取模。
输入输出样例
输入样例 #1
2 1 1
D 1 2
输出样例 #1
1
输入样例 #2
2 1 0
输出样例 #2
2
输入样例 #3
3 2 2
A 1 2
D 1 3
输出样例 #3
2
说明
#### 样例解释 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<N$。