Little P likes positive integers $k$ and lollipops. Little P considers a simple undirected graph to be a "lollipop graph" if and only if:
- For every vertex $i$, there is no vertex $j$ such that $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ and there is an edge between $i$ and $j$.
- For every vertex $i$, there are at most two vertices $j$ such that $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ and there is an edge between $i$ and $j$.
Note that all vertices are numbered starting from $0$.
Little P gave a simple undirected lollipop graph with $n$ vertices to Little W as a gift. However, during transmission, cosmic rays affected the undirected graph. Specifically, each edge has a certain probability of being disconnected by cosmic rays.
After receiving the lollipop graph, Little W defined its "lollipop degree" as $\prod_{i=0}^{n-1}(deg_i+t)$.
Little P wants to know how "lollipop-like" Little W thinks his graph is. However, since he only knows the probability of each edge being disconnected, he has to settle for calculating the expected value of the lollipop degree of the graph after it is transmitted to Little W. Since Little P does not like decimals or large numbers (note that here, "decimals" and "large numbers" are not antonyms!), you only need to tell him the expected value of the lollipop degree modulo $998244353$.
Please pay attention to the constant factor in your code.
Input
The first line contains five integers $n, m, k, t, sub$, where $sub$ represents the subtask number.
The next $m$ lines each contain three integers $u_i, v_i, p_i$, representing an undirected edge between $u_i$ and $v_i$, where the probability of the cosmic ray disconnecting it is $p_i$.
Output
Output a single integer representing the expected value, modulo $998244353$.
Examples
Input 1
3 2 3 0 0 0 1 499122177 1 2 499122177
Output 1
499122177
Input 2
4 4 2 1 0 0 1 3 0 2 4 1 3 5 2 3 6
Output 2
998243917
Input 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
Output 3
446947426
Constraints
| Subtask | Score | Additional Constraints |
|---|---|---|
| 1 | 31 | $n\leq19$ |
| 2 | 13 | $k\leq10$ |
| 3 | 13 | $k\leq14$ |
| 4 | 13 | For every vertex $i$, there is at most one vertex $j$ such that $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ and there is an edge between $i$ and $j$ |
| 5 | 13 | For every vertex $i$, there are at most two vertices $j$ such that $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ and there is an edge between $i$ and $j$ |
| 6 | 17 | None |
For all data: $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$ is given modulo $998244353$, $0\leq u_i,v_i\leq n-1$, $u_i\neq v_i$. The given graph is a lollipop graph.