## 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 ≤ WN), 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 109 + 7.

```2 1 1
D 1 2
```

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

```2 1 0
```

```2
```

### Explanation for Sample 2

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

```3 2 2
A 1 2
D 1 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).

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