### 2014 Canadian Computing Competition, Stage 2

## Day 1, Problem 3: Werewolf

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 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 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

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

`N`(1 ≤`N`≤ 200), the number of robots, followed by`W`(0 ≤`W`≤`N`), the number of werewolves, followed by`M`(0 ≤`M`<`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 robot`a`accused robot`b`of being a werewolf;`D`

`a``b`indicates robot`a`defended robot`b`.

You may assume that for 20% of the marks for this problem, `N` ≤ 20.

### 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

### Sample Output 1

1

### Explanation for Sample 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

### Sample Output 2

2

### Explanation for Sample 2

With no information, either robot 1 or robot 2 could be a werewolf.

### Sample Input 3

3 2 2 A 1 2 D 1 3

### Sample Output 3

2

### Explanation for Sample 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).

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 64M

**Added:** May 17, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

thorthugnastyon Oct 13, 2014 - 5:28:11 am UTC RE Statusbbi5291on Oct 13, 2014 - 6:37:58 am UTC Re: RE Status