Xiao P aime les entiers positifs $k$ et les sucettes. Xiao P considère qu'un graphe non orienté simple est une « sucette » si et seulement si :

• Pour chaque sommet $i$, il n'existe aucun sommet $j$ tel que $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ et qu'il existe une arête entre $i$ et $j$.
• Pour chaque sommet $i$, il existe au plus deux sommets $j$ tels que $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ et qu'il existe une arête entre $i$ et $j$.

Notez que tous les sommets sont numérotés à partir de $0$.

Xiao P a offert à Xiao W un graphe non orienté simple à $n$ sommets qui est une sucette. Cependant, pendant le transfert, des rayons cosmiques ont affecté ce graphe. Plus précisément, chaque arête a une certaine probabilité d'être rompue par les rayons cosmiques.

Après avoir reçu le graphe, Xiao W définit son « degré de sucette » comme étant $\prod_{i=0}^{n-1}(deg_i+t)$.

Xiao P veut savoir à quel point Xiao W trouve son graphe « sucette », mais comme il ne connaît que la probabilité que chaque arête soit rompue, il doit se contenter de calculer l'espérance du degré de sucette du graphe après le transfert. Comme Xiao P n'aime ni les nombres décimaux ni les très grands nombres (notez que « décimal » et « grand nombre » ne sont pas des antonymes ici !), vous devez simplement lui donner la valeur de l'espérance du degré de sucette modulo $998244353$.

Veuillez faire attention à la constante de votre code.

Format d'entrée

La première ligne contient cinq entiers $n, m, k, t, sub$, où $sub$ représente le numéro de la sous-tâche.

Les $m$ lignes suivantes contiennent chacune trois entiers $u_i, v_i, p_i$, indiquant qu'il existe une arête non orientée entre $u_i$ et $v_i$, et que la probabilité qu'elle soit rompue par les rayons cosmiques est $p_i$.

Format de sortie

Affichez un seul entier représentant l'espérance, modulo $998244353$.

Exemples

Entrée 1

3 2 3 0 0
0 1 499122177
1 2 499122177

Sortie 1

499122177

Entrée 2

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

Sortie 2

998243917

Entrée 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

Sortie 3

446947426

Données

Pour toutes les données : $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$ est donné modulo $998244353$, $0\leq u_i,v_i\leq n-1$, $u_i\neq v_i$. Le graphe donné est une sucette.