Đếm đồ thị có hướng

Cho một đồ thị có hướng, không trọng số gồm $n$ đỉnh được đánh số từ $1$ đến $n$ và $m$ cung. Mọi cung của đồ thị đều đi từ đỉnh $v$ tới đỉnh $u$ với $v<u$.

Hãy đếm số cách thêm vào đồ thị một số lượng tuỳ ý (có thể bằng $0$) cung sao cho đồ thị thu được thoả mãn đồng thời các điều kiện sau:

1. Từ đỉnh $i$ bất kỳ ($i<n$) đều đi đến được tất cả các đỉnh $i+1,i+2,\dots ,n$.
2. Mọi cung đi từ đỉnh $v$ tới đỉnh $u$ đều thoả $v<u$.
3. Giữa hai đỉnh bất kỳ có nhiều nhất một cung.
4. Với mọi cặp đỉnh $i,j$ ($i<j$) mà $j-i\le k$, đường đi ngắn nhất từ $i$ đến $j$ gồm đúng $j-i$ cung.
5. Với mọi cặp đỉnh $i,j$ ($i<j$) mà $j-i>k$, đường đi ngắn nhất từ $i$ đến $j$ gồm $j-i$ cung hoặc $j-i-k$ cung.

Hai cách thêm cung được coi là khác nhau nếu tồn tại cặp đỉnh $i,j$ ($i<j$) mà đồ thị thu được theo cách thứ nhất có cung từ $i$ đến $j$, còn đồ thị thu được theo cách thứ hai thì không.

Kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$, $v_i$ mô tả một cung có hướng đi từ đỉnh $u_i$ tới đỉnh $v_i$ trong đồ thị ban đầu.

Dữ liệu bảo đảm giữa mỗi cặp đỉnh $u_i,v_i$ có nhiều nhất một cung, các cung được cho theo thứ tự $u_i$ không giảm, và với cùng một $u_i$ thì các cung được cho theo thứ tự $v_i$ tăng dần.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách thêm cung, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $2\le n\le {10}^6$
• $0\le m\le {10}^5$
• $1\le k\le {10}^6$
• $1\le u_i<v_i\le n$

Ví dụ