Bạn được cho một cây gồm \(n\) đỉnh và \(m\) yêu cầu, mỗi yêu cầu là một đường đi trên cây từ \(u\) đến \(v\). Bạn phải tô mỗi cạnh trên cây bằng một màu từ \(1\) đến \(K\) sao cho với mỗi yêu cầu, đường đi của yêu cầu phải có ít nhất hai màu khác nhau.

Yêu cầu: Đếm số cách tô màu hợp lệ, hai cách tô màu được coi là khác nhau nếu tồn tại một cạnh có màu khác nhau trong hai cách.

Input

• Dòng đầu chứa ba số nguyên dương \(n, m\) và \(k\) \((1 \le n \le 70, 1 \le m \le 15, 1 \le k \le 10^9)\).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n)\) mô tả một cạnh của cây.
• \(m\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(x\) và \(y\) \((1 \leq x, y \leq n)\) mô tả một yêu cầu.

Output

• Một số nguyên là số cách tô màu hợp lệ --- Kết quả của bài toán lấy phần dư khi chia cho \(10 ^ 9 + 7\).

Scoring

• Subtask 1 (\(20\%\) số điểm): \(m = 1\).
• Subtask 2 (\(20\%\) số điểm): \(m = 2\).
• Subtask 3 (\(20\%\) số điểm): Mỗi cạnh trên cây thuộc không quá \(1\) yêu cầu.
• Subtask 4 (\(20\%\) số điểm): \(k = 2\).
• Subtask 5 (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 1 3
1 2
2 3
1 3

6