Маленький 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 подарил маленькому W простой неориентированный «леденцовый» граф с $n$ вершинами. Однако во время передачи космические лучи повлияли на этот граф. А именно, каждое ребро с некоторой вероятностью может быть разорвано космическими лучами.

Получив «леденцовый» граф, маленький W определил его «степень леденцовости» как $\prod_{i=0}^{n-1}(deg_i+t)$.

Маленький P хочет узнать, насколько «леденцовым» маленький W считает его граф, но так как он знает только вероятности разрыва каждого ребра, он может лишь вычислить математическое ожидание степени леденцовости графа после передачи. Поскольку маленький P не любит десятичные дроби и слишком большие числа, вам нужно вывести значение математического ожидания по модулю $998244353$.

Пожалуйста, обратите внимание на константы в вашем коде.

Входные данные

Первая строка содержит пять целых чисел $n, m, k, t, sub$, где $sub$ — номер подзадачи.

Далее следуют $m$ строк, каждая из которых содержит три целых числа $u_i, v_i, p_i$, означающих, что существует неориентированное ребро между $u_i$ и $v_i$, а вероятность того, что космические лучи разорвут его, равна $p_i$.

Выходные данные

Выведите одно целое число — математическое ожидание, взятое по модулю $998244353$.

Примеры

Входные данные 1

3 2 3 0 0
0 1 499122177
1 2 499122177

Выходные данные 1

499122177

Входные данные 2

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

Выходные данные 2

998243917

Входные данные 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

Выходные данные 3

446947426

Ограничения

Для всех данных: $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$ дано по модулю $998244353$, $0\leq u_i, v_i\leq n-1$, $u_i\neq v_i$. Исходный граф является «леденцовым».