Đường đi trong đồ thị I

Cho đồ thị có hướng $n$ đỉnh và $m$ cạnh. Đếm số đường đi từ đỉnh $1$ đến đỉnh $n$ có đúng $k$ cạnh.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$, $m$ và $k$.

• $m$ dòng tiếp theo, mỗi dòng chứa hai số $a$ và $b$ — cạnh từ $a$ đến $b$.

Dữ liệu ra

In số đường đi modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 100$
• $1\le m\le n(n-1)$
• $1\le k\le {10}^9$

Ví dụ