Bạn Khánh là một bạn nhỏ rất thích khám phá các con đường trong khu phố. Khu phố có \(N\) địa điểm vui chơi được đánh số từ \(1\) đến \(N\), và có \(M\) con đường một chiều giữa các địa điểm. Con đường \(u \to v\) cho phép bạn đi từ địa điểm \(u\) sang địa điểm \(v\).

Do khu phố được quy hoạch theo từng khu vực rất rõ ràng, mọi con đường đều đi theo hướng từ khu phía trước sang khu phía sau, nên bản đồ khu phố đảm bảo không có vòng khép kín.

Nhân dịp cuối tuần, Khánh muốn đi từ địa điểm \(S\) đến địa điểm \(T\), và cậu ấy tự đặt cho mình một quy tắc vui: đi đúng \(K\) con đường (tức là đúng \(K\) bước nhảy qua các con đường một chiều). Hỏi có bao nhiêu cách khác nhau để đi từ \(S\) đến \(T\) tuân thủ đúng quy tắc này? Hai cách khác nhau nếu chuỗi con đường sử dụng khác nhau.

Vì số cách có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 5 \cdot 10^3\), \(0 \le M \le 5 \cdot 10^4\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả con đường một chiều từ \(u\) sang \(v\) (\(u \ne v\)).
• Dòng cuối chứa ba số nguyên \(S\), \(T\) và \(K\) (\(1 \le S, T \le N\), \(0 \le K \le 100\)).

Định dạng đầu ra

• Một số nguyên duy nhất là số cách đi đúng \(K\) bước từ \(S\) đến \(T\), modulo \(10^9 + 7\).

Ví dụ

Input:

5 6
1 2
1 3
2 4
3 4
4 5
2 5
1 5 3

Output:

2

Giải thích:

• \(1 \to 2 \to 4 \to 5\)
• \(1 \to 3 \to 4 \to 5\)

Ràng buộc

• \(1 \le N \le 5 \cdot 10^3\)
• \(0 \le M \le 5 \cdot 10^4\) (tổng đầu vào)
• \(0 \le K \le 100\)
• Bản đồ đảm bảo không có vòng khép kín.
• Kết quả in theo modulo \(10^9 + 7\).