늑대인간 게임

시간 제한1초메모리 제한256 MB

요약

정확히 W명이 늑대인간이면서 모든 고발과 변호 조건을 만족하는 역할 배정 수를 1000000007로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

로봇 $N$ 명 중 정확히 $W$ 명이 늑대인간이다. 각 관계는 고발(A) 또는 변호(D)이며 $a < b$ 이다. 늑대인간은 다른 늑대인간을 고발하지 않고, 변호하는 대상은 항상 늑대인간이다. 조건을 만족하는 역할 배정 수를 $10^9+7$ 로 나눈 나머지를 출력한다.

입력

첫 줄에 $N$ , $W$ , $M$ 이 주어진다. 다음 $M$ 줄에 A a b 또는 D a b 형식의 관계가 주어진다.

출력

조건을 만족하는 역할 배정 수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
2 1 1
D 1 2
```
예상 출력
```
1
```
예제 2
입력
```
2 1 0
```
예상 출력
```
2
```
예제 3
입력
```
3 2 2
A 1 2
D 1 3
```
예상 출력
```
2
```