小 $\omega$ 的仙人掌（$\texttt{d}$）

题面描述

小 $\omega$ 有一棵包含 $n$ 个节点 $m$ 条边的无重边无自环边仙人掌。

初始每个点和每条边均有一个权值。

定义一个独立集的权值为被选的点与两端均不被选的边的权值和的 $k$ 次方。

求随机给 $p$ 个不同的点或边的权值加上 $t$ 后，选择每种独立集的权值之和的期望，对 $998244353$ 取模。注意，空集也是独立集。

输入格式

第一行五个整数 $n,m,k,p,t$。

第二行 $n$ 个整数，表示每个点的点权。

接下来 $m$ 行每行三个整数 $u_i,v_i,w_i$，表示每条边的两端与权值。

输出格式

一行，一个正整数，表示随机添加权值后选择每种独立集的权值之和的期望，对 $998244353$ 取模。

样例一

input

3 2 1 0 1
1 1 1
1 2 1
2 3 2

output

11

样例二

input

12 13 7 4 11
123 234 345 456 567 678 789 987 876 765 654 543
1 2 111
2 3 434
3 4 767
4 1 556
4 7 999
3 5 238
5 12 648
5 6 993
6 10 943
10 9 234
8 9 555
8 6 666
11 8 233

output

600203473

样例三

见附件中的 ex_d3.in 和 ex_d3.ans，此样例满足子任务 $8$。

样例四

见附件中的 ex_d4.in 和 ex_d4.ans，此样例满足子任务 $9$。

限制与约定

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\le n\le900,1\le m\le 1800,0\le k,p\leq30$，保证 $t$ 和所有边权均为小于 $998244353$ 的非负整数。