题目描述
Problem Background
You see a strange graph.
Problem Description
There is a simple undirected connected graph with $n$ vertices and $m$ edges, where each vertex can be colored either black or white.
The graph is sparse, specifically, there are two cases:
- $m = n - 1$, which is a tree.
- $m = n$, which is a cycle-rooted tree.
We define the value of a black and white graph as the sum of the $k$-th powers of the sizes of its black connected components.
The structure of the graph is determined, but the color of each vertex is not yet decided. For the $i$-th vertex, there is a $p_i$ percent chance it is black, and otherwise, it is white.
Calculate the expected value of the graph modulo $998244353$.
Input Format
The first line contains three positive integers $n$, $m$, and $k$, as described in the problem statement.
The next line contains $n$ numbers representing $p_{1 \sim n}$.
The following $m$ lines, each containing two numbers $f$ and $t$, represent an undirected edge $f \leftrightarrow t$ in the graph.
Output Format
Output a single integer, which is the expected value of the graph modulo $998244353$.
Sample Input and Output
Sample Input #1
5 4 3
50 50 50 50 50
1 2
2 3
2 4
2 5
Sample Output #1
19
Sample Input #2
6 5 2
20 30 40 50 60 70
1 2
2 3
2 4
2 5
4 6
Sample Output #2
397301258
Sample Input #3
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
Sample Output #3
361859252
Notes
| Data Point | $n$ | $m$ | $k$ | Property 1 | Property 2 | Score |
|---|---|---|---|---|---|---|
| 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$ |
Special Property 1: $p_i = 50$.
Special Property 2: The graph degenerates into a chain, where vertex $i$ is connected to vertex $i+1$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分