시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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).