Werewolf

Time limit1sMemory limit256 MB

Summary

Count the role assignments with exactly W werewolves that satisfy all accusations and defenses, modulo 1000000007.

Level: Medium7 of 10
Topics: Graph, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Among $N$ robots, exactly $W$ are werewolves. Each statement is an accusation (A) or defense (D) with $a < b$ . Werewolves never accuse werewolves, and any robot defended by a werewolf is also a werewolf. Count valid role assignments modulo $10^9+7$ .

Input

The first line contains $N$ , $W$ , and $M$ . The next $M$ lines each contain A a b or D a b.

Output

Print the number of valid assignments modulo $10^9+7$ .

Examples3

Example 1
Input
```
2 1 1
D 1 2
```
Expected output
```
1
```
Example 2
Input
```
2 1 0
```
Expected output
```
2
```
Example 3
Input
```
3 2 2
A 1 2
D 1 3
```
Expected output
```
2
```