Năng Lực Bò (Gold)

Bác John phỏng vấn $N$ con bò xếp thành một hàng, đánh số từ $1$ đến $N$, và cho mỗi con một điểm năng lực nguyên từ $1$ đến $C$. Gọi $c_i$ là điểm năng lực của con bò thứ $i$.

Bác chỉ còn nhớ $Q$ cặp số $(a_i,h_i)$, mỗi cặp mang ý nghĩa: con bò thứ $h_i$ là con bò đầu tiên trong hàng (tức là con có chỉ số nhỏ nhất) có điểm năng lực lớn hơn nghiêm ngặt điểm của tất cả các con bò từ $1$ đến $a_i$.

Hãy đếm số dãy điểm năng lực $(c_1,c_2,\dots ,c_N)$ thỏa mãn đồng thời cả $Q$ ràng buộc, theo modulo ${10}^9+7$. Nếu bác John nhớ nhầm và không có dãy nào thỏa mãn thì đáp án là $0$.

Dữ liệu vào

• Dòng đầu tiên: ba số nguyên $N$, $Q$, $C$.
• $Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a_i$ và $h_i$.

Dữ liệu ra

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

Ràng buộc

• $2\le N\le {10}^9$
• $1\le Q\le min(N-1,100)$
• $1\le C\le {10}^4$
• $1\le a_i<h_i\le N$
• Các cặp được cho theo thứ tự bất kỳ và có thể trùng nhau.

Ví dụ