Trước đầu năm học mới ở trường Hogwart, luôn có một cuộc họp mà tất cả ~n~ giáo viên đều phải tham dự. Mỗi giáo viên là một phù thủy đội một chiếc mũ chóp nhọn, độ cao mũ là một số nguyên từ ~1~ đến ~n~ và khác nhau từng đôi một. Ta xem giáo viên được đánh số theo độ cao mũ, tức là giáo viên ~i~ có mũ cao ~i~. Thầy Hiệu trưởng có mũ cao ~n~ và đã ngồi cố định vào một chỗ trên bàn tròn.

Các giáo viên còn lại lần lượt chọn chỗ ngồi quanh bàn tròn sao cho với mọi cặp người ngồi cạnh nhau, độ cao mũ của họ không chênh lệch quá ~p~, tức là nếu hai người ngồi kề nhau có mũ cao ~u~ và ~v~ thì phải có ~|u-v| \le p~.

Trong cuộc họp, các giấy tờ được chuyền từ mỗi người sang người ngồi ngay bên phải. Không phải ai cũng ưa nhau: nếu phù thủy ~a~ không thích ~b~ thì ~b~ không được ngồi ngay bên phải của ~a~. Có tất cả ~k~ cặp quan hệ như vậy cần tránh.

Yêu cầu

Tính số cách sắp xếp chỗ ngồi cho toàn bộ ~n~ giáo viên quanh bàn tròn (tính theo thứ tự vòng tròn), sau khi vị trí của thầy Hiệu trưởng (mũ ~n~) đã được cố định, sao cho đồng thời thỏa mãn:

• Với mọi cặp người ngồi kề nhau quanh bàn tròn: ~|u-v| \le p~.
• Với mọi cặp cấm ~(a,b)~: người ~b~ không ngồi ngay bên phải của người ~a~.

In kết quả theo mô-đun ~10^9+7~.

Dữ liệu

• Dòng đầu chứa ~3~ số nguyên ~n, k, p~.
• Trong ~k~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i, b_i~ mô tả một cặp cấm có hướng ~(a_i, b_i)~ (tức ~b_i~ không được ngồi ngay bên phải ~a_i~).

Kết quả

In ra một số nguyên: số cách sắp xếp thỏa mãn, lấy theo mô-đun ~10^9+7~.

Ví dụ

Ví dụ 1

Input

5 2 3
1 3
5 4

Output

6

Ràng buộc và chấm điểm

• ~1 \le n \le 10^5~
• ~0 \le k \le 10^5~
• ~0 \le p \le 3~
• ~1 \le a_i, b_i \le n~, ~a_i \ne b_i~
• Không có cặp quan hệ nào trùng nhau.