Tý cần giải bài toán sau:

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.

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

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

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

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

Đầ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\).