小 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$ 取模后的数。
样例
输入格式 1
3 2 3 0 0 0 1 499122177 1 2 499122177
输出格式 1
499122177
输入格式 2
4 4 2 1 0 0 1 3 0 2 4 1 3 5 2 3 6
输出格式 2
998243917
输入格式 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
输出格式 3
446947426
数据范围
| 子任务编号 | 分值 | 额外限制 |
|---|---|---|
| 1 | 31 | $n\leq19$ |
| 2 | 13 | $k\leq10$ |
| 3 | 13 | $k\leq14$ |
| 4 | 13 | 对于每个点 $i$，至多有一个点 $j$ 使得 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ 且 $i$ 与 $j$ 之间有边 |
| 5 | 13 | 对于每个点 $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\leq n-1 $，$u_i\neq v_i$。给定的是一张棒棒糖的图。