Năng Lực Bò (Gold)

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\le N\le {10}^9$, $1\le Q<N$, $1\le C\le {10}^4$).
• $Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $a_i$ và $h_i$ ($1\le a_i<h_i\le 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\le N\le {10}^9$
• $1\le Q<N$
• $1\le C\le {10}^4$

Ví dụ