시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2 2 2 100.000%

## 문제

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.

## 입력

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.

## 출력

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.

## 예제 입력 1

2 1 1
D 1 2


## 예제 출력 1

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

2 1 0


## 예제 출력 2

2


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

## 예제 입력 3

3 2 2
A 1 2
D 1 3


## 예제 출력 3

2


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 robots 2 and 3 to both be werewolves).