Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 3

As they usually do, $N$ robots are playing the game of Werewolf, and the robots are numbered with integers from $1$ to $N$. Exactly $W$ of these robots are werewolves, and the remainder are civilians. Though the game of Werewolf involves various aspects, we will focus on a single discussion phase of the game.

Robots accuse other robots of being werewolves and defend other robots by vouching for their innocence.

The werewolves know each other's identities and:

• A werewolf never accuses another werewolf;
• Any robot that a werewolf defends is another werewolf.

Civilians may accuse or defend either type of robot.

Additional constraints to make our task a bit easier:

• No robot is both accused and defended.
• No robot is accused or defended more than once.
• For a robot $A$ to accuse or defend a robot $B$, then $A<B$.

You will be given all the accusations and defenses between $N$ robots where there are exactly $W$ werewolves. A role assignment identifies each of the robots as either werewolf or civilian. Your goal is to figure out how many role assignments satisfy all the above constraints.

Input Specification

The first line contains three numbers (each separated by one space):

• $N$ $(1\le N\le 200)$, the number of robots, followed by
• $W$ $(0\le W\le N)$, the number of werewolves, followed by
• $M$ $(0\le M\le N)$, the number of accusations/defenses.

The next $M$ lines give the accusations and defenses. Each of these lines will be one of the following two forms:

• $A$ $a$ $b$ indicates that robot $a$ accused robot $b$ of being a werewolf;
• $D$ $a$ $b$ indicates that robot $a$ defended robot $b$.

You may assume that for 20% of the marks for this problem, $N\le 20$.

Output Specification

Output the number of role assignments that are consistent with the given information. Since this number may be very large, you must output this answer modulo ${10}^9+7$.

Sample Input 1

2 1 1
D 1 2

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

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

Sample Input 2

2 1 0

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

With no information, either robot $1$ or robot $2$ could have been a werewolf.

Sample Input 3

3 2 2
A 1 2
D 1 3

Output for Sample Input 3

2

Explanation of Output for Sample Input 3

Either robot $1$ is a werewolf, which implies robot $2$ is a civilian and robot $3$ is a werewolf as well, or robot $1$ is a civilian (which allows robot $2$ and $3$ to both be werewolves).