Nông dân John đang tuyển thêm bò đầu đàn cho đàn bò của mình. Sau khi phỏng vấn, anh ta chấm điểm cho những con bò ứng viên theo thang điểm gọi là "cowmpetency", hay còn gọi là "độ bảnh bò" cho mỗi con bò. Số điểm này dao động từ \(1\) đến \(C\) (\(1 \leq C \leq 10^4\)), với \(C\) là độ bảnh mà John mong muốn con bò đầu đàn của mình có được.

Do đã mệt mỏi sau khi phải phỏng vấn \(N\) con bò được đánh số từ \(1\) đến \(N\) \((2 \leq N \leq 10^9)\), anh John đã quên mất độ bảnh của những con bò ứng viên. Tuy nhiên, anh vẫn nhớ được \(Q\) \((1 \leq Q \leq \text{ min(N - 1,100)})\) cặp số (\(a_i, h_i\)), trong đó bò \(h_i\) là con bò đầu tiên có độ bảnh lớn hơn hẳn các con trong dãy từ bò 1 đến bò \(a_i\) (vậy \(1 \leq a_i < h_i \leq N\)).

Nhiệm vụ của bạn là giúp nông dân John đếm xem có bao nhiêu dãy những con bò thỏa mãn \(Q\) cặp (\(a_i, h_i\)) mà anh ấy đưa ra. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(10^9 + 7\).

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(S\), và \(C\).
• \(Q\) dòng tiếp theo mỗi dòng chứa một cặp số (\(a_i, h_i\)). Dữ liệu đảm bảo tất cả \(a_j\) đều phân biệt.

Output

• Gồm một số nguyên là số lượng đoạn "cowpetency" phù hợp với những gì anh John nhớ, modulo \(10^9 +7\).

Scoring

• Subtask 1: \(N \leq 10\) và \(Q,C \leq 4\)
• Subtask 2: \(N,C \leq 100\)
• Subtask 3: \(N \leq 2000\) và \(C \leq 200\)
• Subtask 4: \(N,C \leq 2000\)
• Subtask 5: Không có ràng buộc gì thêm

Example

6 2 3
2 3
4 5

6

10 1 20
1 3

399988086