Cho một đồ thị có hướng có \(n\) đỉnh và \(m\) cạnh.

Yêu cầu: Tính số đường đi từ đỉnh \(1\) đến đỉnh \(n\) sao cho đường đi đó qua đúng \(k\) cạnh.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m\) và \(k\) \((1 ≤ n ≤ 100; 1 ≤ m ≤ n ; 1 ≤ k ≤ 10^9)\)

• \(m\) dòng tiếp theo mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b (1 ≤ a, b ≤ n)\)

Output

• In ra số lượng đường đi tìm được chia lấy dư cho \(10^9+7\).

Sample Input

3 4 8
1 2
2 3
3 1
3 2

Sample Output

2

Giải thích

• Đường đi thứ 1: 1→2→3→1→2→3→1→2→3

• Đường đi thứ 2: 1→2→3→2→3→2→3→2→3