P14515 [NFLSPC #8] 小 P，小 W，棒棒糖

小 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 | 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