Đồ thị có hướng \(N\) đỉnh. Đếm số đường đi độ dài \(K\) từ \(1\) đến \(N\).

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

• Dòng đầu: \(N, M, K\) (\(1 \le N \le 100\), \(1 \le K \le 10^9\)).
• \(M\) dòng tiếp: \(u, v\).

Định dạng đầu ra

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

Ví dụ

Input:

3 3 2
1 2
2 3
1 3

Output:

2

Ràng buộc

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