Đại học Kyoto có một cái cây biểu tượng tráng lệ.

Bị ấn tượng bởi cái cây này, K-kun đã tạo ra một bản sao của nó dưới dạng một cây có gốc với $N$ đỉnh. Các đỉnh của cây được đánh số từ $1, 2, \dots, N$, gốc của cây là đỉnh $1$, và cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$.

Vì nghĩ rằng việc chỉ sao chép cái cây là không thú vị, K-kun viết một số nguyên không âm lên mỗi đỉnh của cây sao cho các điều kiện sau được thỏa mãn:

Các điều kiện

• Số nguyên được viết trên gốc là $K$.
• Với mỗi đỉnh không phải là gốc, số nguyên được viết trên đỉnh đó nhỏ hơn hoặc bằng số nguyên được viết trên đỉnh cha của nó.

Hãy tìm số dư khi chia số cách gán các số nguyên lên các đỉnh của cây cho $998244353$.

Hai cách gán số nguyên lên các đỉnh được coi là khác nhau nếu và chỉ nếu tồn tại một đỉnh nào đó mà số nguyên được viết trên đỉnh đó khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên $N, K$ cách nhau bởi dấu cách ($2 \le N \le 3000, 1 \le K \le 10^9$).

Mỗi dòng trong số $N - 1$ dòng tiếp theo chứa các số nguyên $u_i, v_i$ cách nhau bởi dấu cách, biểu diễn một cạnh của cây.

Dữ liệu ra

In ra kết quả theo modulo $998244353$.

Ví dụ

Dữ liệu vào 1

5 1
1 2
1 3
3 4
3 5

Dữ liệu ra 1

10

Dữ liệu vào 2

16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1

Dữ liệu ra 2

623173536

Ghi chú

Đối với ví dụ đầu tiên, 10 cách gán số nguyên cho các đỉnh 1, 2, 3, 4, 5 sau đây thỏa mãn các điều kiện:

• 1, 0, 0, 0, 0
• 1, 0, 1, 0, 0
• 1, 0, 1, 0, 1
• 1, 0, 1, 1, 0
• 1, 0, 1, 1, 1
• 1, 1, 0, 0, 0
• 1, 1, 1, 0, 0
• 1, 1, 1, 0, 1
• 1, 1, 1, 1, 0
• 1, 1, 1, 1, 1