小 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 送了一個包含 $n$ 個點的棒棒糖的簡單無向圖給小 W 作為禮物。但是在傳輸過程中，宇宙射線影響了這個無向圖。具體地，每條邊有一定機率被宇宙射線斷開。

小 W 在收到棒棒糖的簡單無向圖後，定義了它的棒棒糖程度 $\prod_{i=0}^{n-1}(deg_i+t)$。

小 P 想知道小 W 認為他的棒棒糖的簡單無向圖有多棒棒糖，但是由於他只知道每條邊斷開的機率，因此他只能退而求其次，計算這個圖在傳給小 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$ 在 $\bmod\ 998244353$ 下給出，$0\leq u_i,v_i\leq n-1 $，$u_i\neq v_i$。給定的是一張棒棒糖的圖。