Mały P lubi dodatnie liczby całkowite $k$ oraz lizaki. Mały P uważa, że prosty graf nieskierowany jest lizakiem wtedy i tylko wtedy, gdy:

• Dla każdego wierzchołka $i$ nie istnieje wierzchołek $j$ taki, że $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ oraz istnieje krawędź między $i$ a $j$.
• Dla każdego wierzchołka $i$ istnieje co najwyżej dwa wierzchołki $j$ takie, że $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ oraz istnieje krawędź między $i$ a $j$.

Zauważ, że wierzchołki są numerowane od $0$.

Mały P podarował małemu W prosty graf nieskierowany będący lizakiem o $n$ wierzchołkach jako prezent. Jednak podczas transmisji promieniowanie kosmiczne wpłynęło na ten graf. Konkretnie, każda krawędź ma określone prawdopodobieństwo zerwania przez promieniowanie kosmiczne.

Po otrzymaniu grafu, mały W zdefiniował jego stopień lizakowatości jako $\prod_{i=0}^{n-1}(deg_i+t)$.

Mały P chce wiedzieć, jak bardzo mały W uważa jego graf za lizak, ale ponieważ zna tylko prawdopodobieństwo zerwania każdej krawędzi, może jedynie obliczyć wartość oczekiwaną stopnia lizakowatości tego grafu po transmisji do małego W. Ponieważ mały P nie lubi liczb ułamkowych ani bardzo dużych liczb, wystarczy podać mu wartość oczekiwaną stopnia lizakowatości modulo $998244353$.

Zwróć uwagę na stałe w swoim kodzie.

Wejście

Pierwsza linia zawiera pięć liczb całkowitych $n, m, k, t, sub$, gdzie $sub$ oznacza numer podzadania.

Następnie $m$ linii, każda zawiera trzy liczby całkowite $u_i, v_i, p_i$, oznaczające, że istnieje krawędź nieskierowana między $u_i$ a $v_i$, a prawdopodobieństwo jej zerwania przez promieniowanie kosmiczne wynosi $p_i$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą wartość oczekiwaną modulo $998244353$.

Przykład

Wejście 1

3 2 3 0 0
0 1 499122177
1 2 499122177

Wyjście 1

499122177

Wejście 2

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

Wyjście 2

998243917

Wejście 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

Wyjście 3

446947426

Dane wejściowe

Dla wszystkich danych: $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$ jest podane modulo $998244353$, $0\leq u_i,v_i\leq n-1$, $u_i\neq v_i$. Podany graf jest lizakiem.