Năng Lực Bò (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác John phỏng vấn $N$ con bò và cho mỗi con một điểm "năng lực" từ $1$ đến $C$ . Bác nhớ $Q$ cặp $(a_{i}, h_{i})$ : con bò thứ $h_{i}$ là con bò đầu tiên có điểm năng lực lớn hơn nghiêm ngặt tất cả các con bò từ $1$ đến $a_{i}$ .

Hãy đếm số dãy điểm năng lực hợp lệ thỏa mãn tất cả các ràng buộc, modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên: ba số nguyên $N$ , $Q$ , $C$ ( $2 \leq N \leq 10^{9}$ , $1 \leq Q < N$ , $1 \leq C \leq 10^{4}$ ).
$Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a_{i}$ và $h_{i}$ ( $1 \leq a_{i} < h_{i} \leq N$ ).

Dữ liệu ra

In một số nguyên duy nhất - số dãy hợp lệ modulo $10^{9} + 7$ .

Ràng buộc

$2 \leq N \leq 10^{9}$
$1 \leq Q < N$
$1 \leq C \leq 10^{4}$

Ví dụ

Input	Output	Giải thích
6 2 3 2 3 4 5	6	6 dãy hợp lệ, ví dụ: [1,1,2,1,3,1], [1,1,2,2,3,1], ...
10 1 20 1 3	399988086	Số dãy hợp lệ mod $10^{9} + 7$ .

Bình luận

Không có bình luận tại thời điểm này.