Bạn được cho một đồ thị có hướng gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) tới \(n\). Hãy đếm số đường đi có \(k\) bước (cạnh) và in ra kết quả theo modulo \(10^9+7\). Một đường đi có thể có ghé thăm các đỉnh và cạnh nhiều lần.

Dữ liệu vào

• Dòng đầu là \(3\) số nguyên \(n,m,k\) \((1 \le n \le 100, 0 \le m \le n.(n-1), 1 \le k \le 10^9)\) lần lượt là số đỉnh, số cạnh và số bước của đường đi.
• \(m\) dòng tiếp theo mô tả các cạnh của đồ thị. Dòng thứ \(i\) gồm \(2\) số nguyên \(a_i,b_i (1 \le a_i, b_i \le n, a_i \neq b_i)\) thể hiện đường đi từ đỉnh \(a_i\) đến đỉnh \(b_i\). Đồ thị đã cho đảm bảo không có khuyên và mỗi cạnh không xuất hiện quá một lần.

Dữ liệu ra

• In ra một dòng chứa số đường đi thoả mãn yêu cầu input theo modulo \(10^9+7\)

Input 1

3 4 2
1 2
2 3
3 1
2 1

Output 1

5

Input 2

5 10 11
2 3
4 2
2 1
2 4
1 5
5 2
3 2
3 1
3 4
1 2

Output 2

21305