Hãy xem xét một đồ thị có hướng gồm \(n\) nút và \(m\) cạnh. Nhiệm vụ của bạn là đếm số lượng đường đi từ nút \(1\) đến nút \(n\) với chính xác \(k\) cạnh.

Input

• Dòng đầu vào đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\): số lượng nút và cạnh và độ dài của đường đi. Các nút được đánh số \(1, 2, \ldots, n\).
• Sau đó, có \(m\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh từ nút \(a\) đến nút \(b\).

Output

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

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq m \leq n(n - 1)\)
• \(1 \leq k \leq 10 ^ 9\)
• \(1 \leq a, b \leq n\)

Example

Sample input

3 4 8  
1 2  
2 3  
3 1  
3 2

Sample output

2

Sample explanation

Các đường đi là \(1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3\) và \(1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3\).