Problem Description

This problem is translated from CCO 2014 Day 1 T3「Werewolf」.

As usual, $N$ robots are playing a game of werewolf. The robots are numbered from $1$ to $N$. Exactly $W$ robots are werewolves, and the rest are villagers. Although the game of werewolf can be studied from different angles, we will focus on just one aspect.

Robots may accuse others of being werewolves, and they may also protect other robots from being falsely accused.

Werewolves know everyone’s roles, and:

• A werewolf never accuses another werewolf.
• Any robot protected by a werewolf is also a werewolf.

Villagers may accuse or protect robots of any type.

Some additional restrictions make the problem easier:

• No robot is both accused and protected.
• No robot is accused or protected more than once.
• If a robot with number $A$ accuses or protects a robot with number $B$, then we guarantee that $A < B$.

You are given all accusation and protection relationships among the $N$ robots, as well as the number of werewolves $W$. Each robot’s role is either werewolf or villager. Your task is to count the number of role assignments that satisfy all the above restrictions.

Input Format

The first line contains three integers $N, W, M$, representing the number of robots, the number of werewolves, and the number of accusation/protection relationships.

The next $M$ lines each describe one relationship. Each line is in one of the following two forms:

• A a b, meaning robot $a$ accuses robot $b$ of being a werewolf.
• D a b, meaning robot $a$ protects robot $b$.

Output Format

Output the number of role assignments that satisfy the conditions above. Since the result can be very large, output it modulo $10^9 + 7$.

2 1 1
D 1 2

1

2 1 0

2

3 2 2
A 1 2
D 1 3

2

Hint

Sample Explanation 1

If robot $1$ is a werewolf, then robot $2$ must also be a werewolf, which would give too many werewolves. The only possibility is that robot $2$ is the only werewolf.

Sample Output 2

If there is no additional protection or accusation information, then both robot $1$ and robot $2$ could be the werewolf.

Sample Explanation 3

If robot $1$ is a werewolf, then robot $2$ will be a villager and robot $3$ will also be a werewolf; or if robot $1$ is a villager, then robots $2$ and $3$ will be werewolves.

For $20\%$ of the testdata, $1 \le N \le 20$.

For $100\%$ of the testdata, $1 \le N \le 200$, $0 \le W \le N$, $0 \le M < N$.

Translated by ChatGPT 5