Background

You saw a strange graph.

Problem Description

There is a simple undirected connected graph with $n$ vertices and $m$ edges. Each vertex can be colored black or white.

This graph is relatively sparse. Specifically, there are two cases.

• $m=n-1$, in which case it is a tree.

• $m=n$, in which case it is a unicyclic graph (a tree with one extra edge).

We define the value of a black-and-white graph as follows: the sum of the $k$-th powers of the sizes of its black connected components.

Now the shape of the graph is fixed, but the color of each vertex is not fixed. For the $i$-th vertex, it has a probability of $p_i$ percent to be black; otherwise it is white.

Compute the expected value of the graph, modulo $998244353$.

Input Format

The first line contains three positive integers $n,m,k$, with meanings as described above.

The next line contains $n$ numbers, which are $p_{1\sim n}$ in order.

The next $m$ lines each contain two numbers $f,t$, indicating an undirected edge $f\leftrightarrow t$ in the graph.

Output Format

Output one integer, the expected value of the graph modulo $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

Hint

Special Property $1$: $p_i=50$.

Special Property $2$: The graph degenerates into a single chain, where there is an edge between $i$ and $i+1$.

Translated by ChatGPT 5