A Xiao P le gustan los enteros positivos $k$ y las paletas. Xiao P considera que un grafo simple no dirigido es una "paleta" si y solo si:
- Para cada vértice $i$, no existe un vértice $j$ tal que $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ y exista una arista entre $i$ y $j$.
- Para cada vértice $i$, existen a lo sumo dos vértices $j$ tales que $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ y exista una arista entre $i$ y $j$.
Nótese que todos los vértices están numerados comenzando desde $0$.
Xiao P le regaló a Xiao W un grafo simple no dirigido que es una paleta con $n$ vértices. Sin embargo, durante la transmisión, los rayos cósmicos afectaron al grafo. Específicamente, cada arista tiene una cierta probabilidad de ser desconectada por los rayos cósmicos.
Después de recibir el grafo, Xiao W define su "grado de paleta" como $\prod_{i=0}^{n-1}(deg_i+t)$.
Xiao P quiere saber qué tan "paleta" considera Xiao W que es su grafo, pero como solo conoce la probabilidad de que cada arista se desconecte, debe conformarse con calcular la esperanza del grado de paleta del grafo después de ser transmitido a Xiao W. Como a Xiao P no le gustan los números decimales ni los números grandes (¡nótese que aquí "decimales" y "grandes" no son antónimos!), solo necesitas decirle el valor de la esperanza del grado de paleta módulo $998244353$.
Por favor, ten en cuenta las constantes de tu código.
Entrada
La primera línea contiene cinco enteros $n, m, k, t, sub$, donde $sub$ indica el número de la subtarea.
Las siguientes $m$ líneas contienen tres enteros $u_i, v_i, p_i$, lo que significa que hay una arista no dirigida entre $u_i$ y $v_i$, y la probabilidad de que los rayos cósmicos la desconecten es $p_i$.
Salida
Imprime una línea con un solo entero, que representa la esperanza, módulo $998244353$.
Ejemplos
Entrada 1
3 2 3 0 0 0 1 499122177 1 2 499122177
Salida 1
499122177
Entrada 2
4 4 2 1 0 0 1 3 0 2 4 1 3 5 2 3 6
Salida 2
998243917
Entrada 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
Salida 3
446947426
Restricciones
| Subtarea | Puntuación | Restricciones adicionales |
|---|---|---|
| 1 | 31 | $n\leq19$ |
| 2 | 13 | $k\leq10$ |
| 3 | 13 | $k\leq14$ |
| 4 | 13 | Para cada vértice $i$, existe a lo sumo un vértice $j$ tal que $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ y existe una arista entre $i$ y $j$ |
| 5 | 13 | Para cada vértice $i$, existen a lo sumo dos vértices $j$ tales que $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ y existe una arista entre $i$ y $j$ |
| 6 | 17 | Ninguna |
Para todos los datos: $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$ se da módulo $998244353$, $0\leq u_i,v_i\leq n-1$, $u_i\neq v_i$. El grafo dado es una paleta.