Problem Description

This problem is translated from CCO 2014 Day1 T3 "Werewolf"

As usual, $N$ robots are playing the werewolf game, numbered from $1$ to $N$. $W$ robots play as werewolves, and the rest play as civilians. Although the werewolf game includes different roles, we will focus on only one of them.

Robots accuse others of being werewolves and protect themselves from being wrongly accused.

Werewolves know the roles of others and:

• A werewolf never accuses another werewolf;
• Any werewolf robot protects only other werewolf robots.

Civilians may accuse or protect any type of robot.

Some additional constraints simplify the problem:

• 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 $A < B$.

You will know all the accusation and protection relationships among the $N$ robots and the number of werewolves, $W$. Each robot's role is either a werewolf or a civilian. Your goal is to calculate the number of valid role assignment schemes that satisfy the above constraints.

Input Format

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

The next $M$ lines describe each relationship, each line being one of the following formats:
- A a b, indicating that robot $a$ accuses robot $b$ of being a werewolf.
- D a b, indicating that robot $a$ protects robot $b$.

Output Format

Output the number of valid role assignment schemes that satisfy the above conditions. The result may be very large, so it needs to be modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

2 1 1
D 1 2

Sample Output #1

1

Sample Input #2

2 1 0

Sample Output #2

2

Sample Input #3

3 2 2
A 1 2
D 1 3

Sample Output #3

2

Notes/Hints

Sample Explanation 1

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

Sample Output 2

Without additional protection or accusation information, both robot $1$ and robot $2$ could be werewolves.

Sample Explanation 3

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

For $20\%$ of the data, $1 \le N \le 20$;

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

见题面 Input 部分

见题面 Output 部分