1. Phát biểu bài toán

Mạng lưới đường ống chân không của thành phố là một đồ thị vô hướng liên thông không có chu trình (một cây) gồm ~N~ trạm (~N \ge 3~), đánh số từ 1 đến ~N~. Trạm được gọi là trạm ngoại vi (lá) nếu nó chỉ nối với đúng 1 đường ống; ngược lại được gọi là trạm trung chuyển (đỉnh trong). Có tất cả ~N - 1~ đường ống, đường ống thứ ~i~ nối hai trạm ~u_i~ và ~v_i~, hiện đang có áp suất dư là một số nguyên không âm ~W_i~.

Một chiến dịch cân bằng áp suất bao gồm một chuỗi hữu hạn các bước. Ở mỗi bước, hệ thống chọn hai trạm ngoại vi (lá) khác nhau ~a~ và ~b~, và giảm áp suất dư của tất cả các đường ống nằm trên đường đi đơn duy nhất từ ~a~ đến ~b~ đi đúng 1 đơn vị.

Mạng lưới được gọi là tự cân bằng hoàn toàn nếu tồn tại một chiến dịch đưa áp suất dư của tất cả ~N - 1~ đường ống về đúng bằng 0 (không có đường ống nào bị âm trong suốt quá trình).

Hiện tại, do lỗi truyền tin, có một số đường ống bị mất dữ liệu áp suất (được ký hiệu bởi ~W_i = -1~). Biết rằng mỗi đường ống bị mất dữ liệu có giá trị thực tế là một số nguyên nằm trong đoạn ~[0, M]~.

Yêu cầu: Hãy đếm số cách gán giá trị nguyên trong đoạn ~[0, M]~ cho tất cả các đường ống có ~W_i = -1~ sao cho mạng lưới thu được là tự cân bằng hoàn toàn. Kết quả chia lấy dư cho 998244353.

2. Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~3 \le N \le 3000~; ~0 \le M \le 3000~).
• ~N - 1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, W_i~ (~1 \le u_i, v_i \le N~; ~W_i = -1~ hoặc ~0 \le W_i \le M~). Dữ liệu đảm bảo đồ thị là một cây.

3. Kết quả

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

4. Ví dụ

Ví dụ 1:

• Input:

3 2
1 2 -1
2 3 -1

• Output:

3

Ví dụ 2:

• Input:

4 2
1 2 1
2 3 -1
2 4 1

• Output:

2

5. Subtasks

• Subtask 1 (15% số điểm): Cây là một đường thẳng.
• Subtask 2 (25% số điểm): Không có cạnh nào bằng ~-1~.
• Subtask 3 (30% số điểm): ~N, M \le 200~.
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm (~N, M \le 3000~).