Farmer John đang tuyển thủ lĩnh mới cho đàn bò. Vì vậy, ông đã phỏng vấn \(N\) (\(2 \leq N \leq 10^9\)) con bò cho vị trí này. Sau mỗi cuộc phỏng vấn, ông gán cho ứng viên một điểm "cowmpetency" nguyên từ \(1\) đến \(C\) (\(1 \leq C \leq 10^4\)), tương quan với năng lực lãnh đạo của ứng viên.

Vì đã phỏng vấn quá nhiều bò, Farmer John quên hết điểm của chúng. Tuy nhiên, ông nhớ \(Q\) (\(1 \leq Q \leq \min(N-1,100)\)) cặp số \((a_i,h_i)\), trong đó bò \(h_i\) là con bò đầu tiên có điểm lớn hơn nghiêm ngặt điểm của tất cả các con bò từ \(1\) đến \(a_i\) (do đó \(1 \leq a_i < h_i \leq N\)).

Farmer John cho bạn \(Q\) cặp \((a_i,h_i)\). Hãy giúp ông đếm số dãy điểm cowmpetency phù hợp với những thông tin này! Đảm bảo có ít nhất một dãy như vậy. Vì số lượng có thể rất lớn, hãy in kết quả theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(N\), \(Q\) và \(C\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một cặp \((a_i,h_i)\). Đảm bảo mọi \(a_j\) đôi một khác nhau.

Dữ liệu ra

In số dãy điểm cowmpetency phù hợp với những gì Farmer John nhớ, theo modulo \(10^9+7\).

Ví dụ

6 2 3
2 3
4 5

6

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 3

399988086

Phân nhóm

• Các test 3-4 thỏa mãn \(N \leq 10\) và \(Q,C \leq 4\).
• Các test 5-7 thỏa mãn \(N,C \leq 100\).
• Các test 8-10 thỏa mãn \(N \leq 2000\) và \(C \leq 200\).
• Các test 11-15 thỏa mãn \(N,C \leq 2000\).
• Các test 16-20 không có ràng buộc bổ sung.

Nguồn

USACO 2024 January Contest, Gold — Cowmpetency: https://usaco.org/index.php?page=viewproblem2&cpid=1378

Tác giả đề: Suhas Nagar