Bản đồ hành chính gồm \(N\) tỉnh, giữa các tỉnh có đường biên giới chung tạo thành cấu trúc cây. Người ta muốn tô màu bản đồ sao cho hai tỉnh có chung đường biên giới không trùng màu. Cho trước bảng màu gồm \(K\) màu khác nhau.

Hãy đếm số cách tô màu thỏa mãn yêu cầu, modulo \(10^9 + 7\).

\(|1| \le 20\) | \(\le 5\) | 10 | | 2 | \(N \le 5000\) | \(Q \le 100\) | 20 | \(|3| \le 2 \cdot 10^5\) | \(\le 10^9\) | 30 | \(|4| \le 2 \cdot 10^5\) | \(\le 10^9\) | 40 |

Đầu vào:

• Dòng đầu gồm hai số \(N\), K (\(1 \le K \le 10^9\)). - N - \(1\) dòng sau, mỗi dòng gồm \(u, v\).

Đầu ra:

• Một số nguyên là số cách tô màu modulo \(10^9 + 7\).

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le N, K \le 10^5\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra số cách tô màu cây bằng \(K\) màu modulo \(10^9+7\) sao cho 2 đỉnh kề nhau khác màu.

Ví dụ

Input:

3 3
1 2
1 3

Output:

12

Giải thích: Đỉnh 1 có 3 cách chọn màu, mỗi đỉnh con có 2 cách chọn màu \(\implies 3 \times 2 \times 2 = 12\).

Ràng buộc & Subtasks