Pさんは正の整数 $k$ とキャンディ（棒棒糖）が好きです。Pさんは、ある単純無向グラフが「キャンディグラフ」であるとは、以下の条件を満たすことだと考えています。
- すべての頂点 $i$ について、 $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$ を満たす頂点 $j$ との間に辺が存在しない。
- すべての頂点 $i$ について、 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$ を満たす頂点 $j$ との間に存在する辺は高々2本である。
なお、すべての頂点は $0$ から番号付けされています。
Pさんは $n$ 個の頂点を持つキャンディグラフを、贈り物としてWさんに送りました。しかし、輸送中に宇宙線がこの無向グラフに影響を与えました。具体的には、各辺はある確率で宇宙線によって切断されます。
Wさんがキャンディグラフを受け取った後、その「キャンディ度」を $\prod_{i=0}^{n-1}(deg_i+t)$ と定義しました。
PさんはWさんが彼のキャンディグラフをどれほどキャンディだと感じたかを知りたいのですが、各辺が切断される確率しか知らないため、Wさんに届いた後のキャンディ度の期待値を計算することにしました。Pさんは小数や大きな数を好まないため（ここで言う小数と大きな数は対義語ではありません！）、キャンディ度の期待値を $998244353$ で割った余りを求めてください。
コードの定数倍に注意してください。
入力形式
1行目に5つの整数 $n, m, k, t, sub$ が与えられます。ここで $sub$ はサブタスク番号を表します。
続く $m$ 行には、それぞれ3つの整数 $u_i, v_i, p_i$ が与えられます。これは $u_i$ と $v_i$ の間に無向辺が存在し、宇宙線によって切断される確率が $p_i$ であることを示します。
出力形式
期待値を $998244353$ で割った余りを1行で出力してください。
入出力例
入力 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
制約
| 子タスク番号 | 配点 | 追加制約 |
|---|---|---|
| 1 | 31 | $n\leq19$ |
| 2 | 13 | $k\leq10$ |
| 3 | 13 | $k\leq14$ |
| 4 | 13 | すべての頂点 $i$ について、 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ を満たす頂点 $j$ との間に存在する辺は高々1本 |
| 5 | 13 | すべての頂点 $i$ について、 $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$ を満たす頂点 $j$ との間に存在する辺は高々2本 |
| 6 | 17 | なし |
すべてのデータについて：$2\leq k\leq 19$、$k\leq n\leq100$、$m\leq 500$、$0\leq t<10^8$、$p$ は $\bmod\ 998244353$ で与えられる、$0\leq u_i,v_i\leq n-1$、$u_i\neq v_i$。与えられるグラフはキャンディグラフである。