Bé Loopy có một cây với cây là đồ thị vô hướng, liên thông và không có chu trình. Loopy muốn tô màu cây này bằng hộp màu có c màu, các màu này hoàn toàn khác nhau và Loopy muốn tô mỗi đỉnh một màu. Vì tô màu bình thường quá nhàm chán nên bé Loopy muốn tô màu sao cho hai đỉnh kề nhau không được tô cùng màu. Bạn hãy đếm số cách tô màu thỏa mãn điều kiện trên, kết quả modulo 998244353.

Dòng đầu tiên chứa số nguyên k (1 ≤ k ≤ 3) — số thứ tự của subtask chứa test này.

Dòng thứ hai chứa hai số nguyên n và c (1 ≤ n ≤ 3·10⁵, 1 ≤ c ≤ 10⁹), lần lượt là số đỉnh của cây và số màu trong hộp để Loopy lựa. Trong n - 1 dòng cuối cùng, mỗi dòng chứa hai số nguyên h và k (1 ≤ h, k ≤ n) mô tả một cạnh của cây.

In ra một số nguyên duy nhất là số cách tô màu cây hợp lệ modulo 998244353.

• Subtask 1: n, c ≤ 300. 

• Subtask 2: Cây có n - 1 cạnh (1, 2), (2, 3), ..., (n - 1, n).

• Subtask 3: Không có ràng buộc gì thêm.