Xét một đồ thị có hướng có n nút và m cạnh. Nhiệm vụ của bạn là đếm số đường đi từ nút 1 đến nút n có đúng k cạnh.

Input

Dòng đầu tiên chứa ba số nguyên n, m và k: số nút, cạnh và độ dài của đường đi. Các nút được đánh số 1,2,~\dots~,n.

Khi đó có m dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên u và v: có một cạnh từ nút u đến nút v.

Output

In số đường đi modulo ~10^9+7~.

Hạn chế

~1 \le n \le 100~

~1 \le m \le n(n-1)~

~1 \le k \le 10^9~

~1 \le u, v \le n~

Examples

Input

3 4 8
1 2
2 3
3 1
3 2

Output

2

Giải thích: Các đường đi là

~1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3~

~1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3.~