#P4815. [CCO2014] 狼人游戏

[CCO2014] 狼人游戏

题目描述

本题译自 CCO 2014 Day1 T3「Werewolf

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

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

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

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

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

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

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

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

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

  • 如果有一个编号为 AA 机器人指控或保护编号为 BB 的机器人,那么我们保证A<BA<B

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

输入格式

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

接下来 MM 行每行描述一个关系,接下来每行都是以下两个形式之一:

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

输出格式

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

2 1 1
D 1 2
1
2 1 0
2
3 2 2
A 1 2
D 1 3
2

提示

样例解释 1

如果机器人 11 是狼人,机器人 22 也必须是,那么狼人就太多了!唯一的可能是机器人 22 是唯一的狼人。

样例输出 2

没有额外的保护或指控信息的话,机器人 11 和机器人 22 都可能是狼人。

样例解释 3

如果机器人 11 是狼人,机器人 22 将是市民,机器人 33 也是狼人;或者机器人 11 是市民,那么机器人 2233 将是狼人。

对于 20%20\% 的数据,1N201\le N\le 20

对于 100%100\% 的数据,1N200,1\le N\le 200, 0WN,0\le W\le N, 0M<N0\le M<N