레이팅 미적용농부 존은 소들의 새 무리 대장을 뽑으려 한다. 이를 위해 \(N\)마리 (\(2 \leq N \leq 10^9\))의 소를 면접했다. 각 면접이 끝난 뒤, 지원자의 리더십 능력과 관련된 \(1\) 이상 \(C\) 이하 (\(1 \leq C \leq 10^4\))의 정수 "소 역량" 점수를 매겼다.
너무 많은 소를 면접했기 때문에 농부 존은 모든 소 역량 점수를 잊어버렸다. 하지만 \(Q\) (\(1 \leq Q \leq \min(N - 1, 100)\))개의 수 쌍 \((a_i, h_i)\)는 기억하는데, 이는 소 \(h_i\)가 소 \(1\)부터 \(a_i\)까지의 모든 소보다 순 크게(strictly greater) 높은 소 역량 점수를 가진 첫 번째 소였다는 뜻이다 (따라서 \(1 \leq a_i < h_i \leq N\)).
농부 존이 \(Q\)개의 쌍 \((a_i, h_i)\)를 알려 준다. 이 정보와 모순되지 않는 소 역량 점수 수열의 개수를 세어 존을 도와주자! 그런 수열이 적어도 하나 존재함이 보장된다. 이 수는 매우 클 수 있으므로 \(10^9 + 7\)로 나눈 나머지를 출력한다.
출제: Suhas Nagar
배점
- 입력 3-4: \(N \leq 10\), \(Q, C \leq 4\).
- 입력 5-7: \(N, C \leq 100\).
- 입력 8-10: \(N \leq 2000\), \(C \leq 200\).
- 입력 11-15: \(N, C \leq 2000\).
- 입력 16-20: 추가 제약 없음.
출제: Suhas Nagar
첫째 줄에 \(N\), \(Q\), \(C\)가 주어진다.
다음 \(Q\)개의 줄에 각각 쌍 \((a_i, h_i)\)가 주어진다. 모든 \(a_j\)는 서로 다름이 보장된다.
농부 존이 기억하는 정보와 모순되지 않는 소 역량 점수 수열의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.
6 2 3
2 3
4 56The following six sequences are the only ones consistent with what Farmer John
remembers:
1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3
10 1 20
1 3399988086Make sure to output the answer modulo \(10^9+7\).