頁面無法載入？點擊這裡可能會修復。
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

需要登入才能撰寫程式碼。