题目描述

小 P 喜欢正整数 $k$ 和棒棒糖。小 P 认为一个简单无向图是棒棒糖的当且仅当：

• 对于每个点 $i$，不存在点 $j$ 使得 $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ 且 $i$ 与 $j$ 之间有边。
• 对于每个点 $i$，至多有两个点 $j$ 使得 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ 且 $i$ 与 $j$ 之间有边。

注意，所有点由 $0$ 开始编号。

小 P 送了一个包含 $n$ 个点的棒棒糖的简单无向图给小 W 作为定情信物礼物。但是在传输过程中，宇宙射线影响了这个无向图。具体地，有每条边有一定概率被宇宙射线断开。

小 W 在收到棒棒糖的简单无向图后，定义了它的棒棒糖程度 $\prod_{i=0}^{n-1}(deg_i+t)$。

小 P 想知道小 W 认为他的棒棒糖的简单无向图有多棒棒糖，但是由于他只知道每条边断开的概率，因此他只能退而求其次，计算这个图在传给小 W 之后棒棒糖程度的期望。由于小 P 不喜欢小数与大数（注意此处小数与大数不是反义词！），所以你只需要告诉他棒棒糖程度的期望对 $998244353$ 取模之后的值即可。

请注意你的代码常数。

输入格式

第一行五个整数 $n,m,k,t,sub$，其中 $sub$ 表示子任务编号。

接下来 $m$ 行，每行三个整数 $u_i,v_i,p_i$ 表示有一条 $u_i,v_i$ 之间的无向边，宇宙射线断开它的概率是 $p_i$。

输出格式

输出一行一个整数，表示期望，对 $998244353$ 取模后的数。

3 2 3 0 0
0 1 499122177
1 2 499122177

499122177

4 4 2 1 0
0 1 3
0 2 4
1 3 5
2 3 6

998243917

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

446947426

提示

数据范围

子任务编号	分值	额外限制
1	31	$n\leq19$
2	13	$k\leq10$
3		$k\leq14$
4		对于每个点 $i$，至多有一个点 $j$ 使得 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ 且 $i$ 与 $j$ 之间有边
5		对于每个点 $i$，至多有两个点 $j$ 使得 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ 且 $i$ 与 $j$ 之间有边
6	17	无

对于所有数据：$2\leq k\leq 19$，$k\leq n\leq100$，$m\leq 500$，$0\leq t<10^8$，$p$ 在 $\bmod\ 998244353$ 下给出，$0\leq u_i,v_i<n$，$u_i\neq v_i$。给定的是一张棒棒糖的图。