페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6220
서브태스크

하마 대장 2s 1024MB

문제

정올이는 하마들을 위한 새로운 대장을 선택하고 있다. 이를 위해 그는 N마리의 하마를 인터뷰했다. 각 인터뷰 후, 그는 후보자에게 1부터 C사이의 정수로 "하마 능력치" 점수를 부여했는데, 이는 리더십 능력과 관련이 있다.

정올이는 많은 하마를 인터뷰했기 때문에 모든 하마의 능력치 점수를 잊어버렸다. 하지만 그는 Q 쌍의 숫자 (a_i, h_i)를 기억하고 있다. 여기서 하마 h_i는 1부터 a_i까지의 하마들보다 점수가 첫 번째로 더 높은 하마다 (따라서 1≤a_i<h_i≤N).

Q 쌍의 (a_i, h_i)를 바탕으로 정올이가 얼마나 많은 점수 시퀀스를 선택할 수 있는지 계산해 보자! 최소한 하나의 가능한 시퀀스가 존재하는 것이 보장된다. 이 숫자는 매우 클 수 있으므로 10^9+7로 나눈 값을 출력하라.


입력

첫 번째 줄에는 N, Q, C가 주어진다.

다음 Q줄에는 각각 (a_i, h_i) 쌍이 주어진다.

[제약 조건]

  • 2≤N≤10^9

  • 1≤C≤10^4

  • 1≤Q≤min(N−1,100)

  • 모든 a_j는 서로 다르다.


출력

정올이가 기억하는 정보와 일치하는 점수 시퀀스의 수를 10^9+7로 나눈 값을 출력하라.


부분문제

번호 점수 조건
#19점

N≤10; Q,C≤4

#218점

N,C≤100

#327점

N≤2000; C≤200

#436점

N,C≤5000

#510점

추가 제약 조건 없음


예제 #1

5 2 3
1 2
3 4
6

가능한 여섯 시퀀스들은 아래와 같다.

  • 1 2 1 3 1

  • 1 2 1 3 2

  • 1 2 1 3 3

  • 1 2 2 3 1

  • 1 2 2 3 2

  • 1 2 2 3 3


예제 #2

10 1 10
1 3
649999993


출처

USACO 2024 January Gold

로그인해야 코드를 작성할 수 있어요.