题目背景

你看见了一张奇怪的图。

题目描述

有一张 $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

提示

特殊性质 $1$ ：$p_i=50$。

特殊性质 $2$ ：图退化成一条链，其中 $i$ 向 $i+1$ 连边。