Đếm Hành Trình Đúng K Cạnh

Cho đồ thị có hướng đơn. Hãy đếm tổng số walk có đúng $k$ cạnh, với đỉnh đầu và đỉnh cuối tùy ý; một walk được phép đi qua lại cùng đỉnh hoặc cạnh nhiều lần.

Input

• Dòng đầu chứa ba số nguyên $n,m,k$.
• Mỗi trong $m$ dòng tiếp theo chứa một cạnh có hướng $u$ $v$, nghĩa là đi từ $u$ đến $v$.

Output

• In tổng số walk có đúng $k$ cạnh, lấy modulo $1000000007$.

Constraints

• $1\le n\le 100$.
• $0\le m\le n$($n-1$).
• $1\le k\le 10^9$.
• Không có cạnh tự khép và không có hai cạnh trùng cùng hướng.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 20$ và $k\le 10^4$.
• Subtask $2$ ($50\%$ số điểm): không có giới hạn bổ sung.

Example

2 2 3
1 2
2 1

2