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\ne 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