Cho đồ thị có hướng \(N\) đỉnh, \(M\) cạnh. Đếm số đường đi từ \(S\) đến \(T\) có độ dài đúng \(K\).

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

• Dòng đầu: \(N, M, S, T, K\) (\(1 \le N \le 100\), \(0 \le M \le N^2\), \(1 \le K \le 10^9\)).
• \(M\) dòng tiếp: mỗi dòng \(u, v\).

Định dạng đầu ra

• Một số nguyên modulo \(10^9+7\).

Ví dụ

Input:

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

Output:

2

Ràng buộc

• 100% số điểm: \(N \le 100\).