Tiểu P thích các số nguyên dương $k$ và kẹo mút. Tiểu P cho rằng một đồ thị vô hướng đơn là đồ thị kẹo mút khi và chỉ khi:
- Với mỗi đỉnh $i$, không tồn tại đỉnh $j$ sao cho $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ và có cạnh nối giữa $i$ và $j$.
- Với mỗi đỉnh $i$, có tối đa hai đỉnh $j$ sao cho $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ và có cạnh nối giữa $i$ và $j$.
Lưu ý rằng các đỉnh được đánh số bắt đầu từ $0$.
Tiểu P đã tặng một đồ thị vô hướng đơn là đồ thị kẹo mút với $n$ đỉnh cho Tiểu W làm quà. Tuy nhiên, trong quá trình truyền tin, tia vũ trụ đã ảnh hưởng đến đồ thị này. Cụ thể, mỗi cạnh có một xác suất nhất định bị tia vũ trụ làm đứt.
Sau khi nhận được đồ thị kẹo mút, Tiểu W định nghĩa độ kẹo mút của nó là $\prod_{i=0}^{n-1}(deg_i+t)$.
Tiểu P muốn biết Tiểu W đánh giá đồ thị kẹo mút của mình "kẹo mút" đến mức nào, nhưng vì anh ấy chỉ biết xác suất mỗi cạnh bị đứt, nên anh ấy chỉ có thể tính kỳ vọng của độ kẹo mút sau khi đồ thị được truyền đến Tiểu W. Vì Tiểu P không thích số thập phân và số lớn (lưu ý ở đây số thập phân và số lớn không phải là từ trái nghĩa!), bạn chỉ cần cho anh ấy biết giá trị kỳ vọng của độ kẹo mút sau khi lấy modulo $998244353$.
Vui lòng chú ý đến hằng số trong mã nguồn của bạn.
Dữ liệu vào
Dòng đầu tiên gồm năm số nguyên $n, m, k, t, sub$, trong đó $sub$ là số hiệu của nhiệm vụ con.
$m$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u_i, v_i, p_i$ biểu thị một cạnh vô hướng giữa $u_i$ và $v_i$, với $p_i$ là xác suất cạnh đó bị tia vũ trụ làm đứt.
Dữ liệu ra
In ra một số nguyên duy nhất là giá trị kỳ vọng, sau khi đã lấy modulo $998244353$.
Ví dụ
Dữ liệu vào 1
3 2 3 0 0 0 1 499122177 1 2 499122177
Dữ liệu ra 1
499122177
Dữ liệu vào 2
4 4 2 1 0 0 1 3 0 2 4 1 3 5 2 3 6
Dữ liệu ra 2
998243917
Dữ liệu vào 3
6 12 3 114514 0 0 1 1 0 2 9 1 2 2 0 3 6 0 4 8 1 4 17 1 5 1 2 5 9 2 3 5 3 4 3 4 5 6 3 5 15
Dữ liệu ra 3
446947426
Nhiệm vụ con
| Nhiệm vụ con | Điểm | Giới hạn bổ sung |
|---|---|---|
| 1 | 31 | $n\leq19$ |
| 2 | 13 | $k\leq10$ |
| 3 | 13 | $k\leq14$ |
| 4 | 13 | Với mỗi đỉnh $i$, có tối đa một đỉnh $j$ sao cho $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ và có cạnh nối giữa $i$ và $j$ |
| 5 | 13 | Với mỗi đỉnh $i$, có tối đa hai đỉnh $j$ sao cho $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ và có cạnh nối giữa $i$ và $j$ |
| 6 | 17 | Không có |
Với tất cả dữ liệu: $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$ được cho dưới dạng modulo $998244353$, $0\leq u_i,v_i\leq n-1$, $u_i\neq v_i$. Đồ thị được cho là một đồ thị kẹo mút.