[CmdOI2019] 黑白图

你看见了一张奇怪的图。

有一张 $n$ 个点，$m$ 条边的简单无向连通图，点可以染上黑色或者白色。 这个图比较稀疏，具体来讲有两种情况。 - $m=n-1$ ，此时是一棵树。 - $m=n$ ，此时是一颗基环树。 我们定义一张黑白图的权值为：其黑色**连通块大小**的 $k$ 次方和。 现在图的形态已经确定，但是每个点上的颜色尚未确定，对于第 $i$ 个点。其有**百分之** $p_i$ 的可能是黑色，反之则是白色。 求图的期望权值对 $998244353$ 取模的结果。

第一行包括三个正整数 $n,m,k$ ，意义如题面所述。 接下来一行 $n$ 个数依次表示 $p_{1\sim n}$。 后 $m$ 行，每行两个数 $f,t$ ，表示图的一条无向边 $f\leftrightarrow t$ 。

输出一个整数，表示图的期望权值对 $998244353$ 取模的结果。

5 4 3
50 50 50 50 50
1 2
2 3
2 4
2 5

19

6 5 2
20 30 40 50 60 70
1 2
2 3
2 4
2 5
4 6

397301258

10 10 2
39 76 71 86 36 38 36 44 63 37 
4 5
2 10
6 10
1 8
5 10
8 10
7 10
3 10
10 9
5 3

361859252

| 数据点编号 | $n$ | 　$m$　 | 　$k$　 | 性质1 | 性质2 | 分数 | | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | 1 | $16$ | $n-1$ | $5$ | $\sqrt{}$ | - | $5$ | | 2 | $50$ | $n-1$ | $3$ | $\sqrt{}$ | $\sqrt{}$ | $5$ | | 3 | $50$ | $n-1$ | $5$ | $\sqrt{}$ | - | $5$ | | 4 | $500$ | $n-1$ | $1$ | - | - | $5$ | | 5 | $2\times 10^5$ | $n-1$ | $3$ | $\sqrt{}$ | $\sqrt{}$ | $5$ | | 6 | $2\times 10^5$ | $n-1$ | $2$ | - | $\sqrt{}$ | $5$ | | 7 | $2\times 10^5$ | $n-1$ | $4$ | - | - | $10$ | | 8 | $16$ | $n$ | $3$ | - | - | $10$ | | 9 | $500$ | $n$ | $3$ | - | - | $10$ | | 10 | $50000$ | $n$ | $2$ | - | - | $10$ | | 11 | $2\times 10^5$ | $n$ | $4$ | $\sqrt{}$ | - | $10$ | | 12 | $2\times 10^5$ | $n$ | $5$ | - | - | $10$ | | 13 | $2\times 10^5$ | $n$ | $5$ | - | - | $10$ | 特殊性质 $1$ ：$p_i=50$。 特殊性质 $2$ ：图退化成一条链，其中 $i$ 向 $i+1$ 连边。