Expected Weight of Black‐White Graph Components

Given a simple, undirected, connected graph with n vertices and m edges – where the graph is either a tree (m = n-1) or a unicyclic graph (m = n) – each vertex is independently colored black with probability \(p_i\%\) and white with probability \(100-p_i\%\). We define the weight of a black‐white graph as the sum over every connected component (induced by black vertices) of the component size raised to the power \(k\), i.e.,

[ \text{weight} = \sum_{\text{black connected components } C} \left(|C|\right)^k. ]

Calculate the expected weight of the graph. Since the answer can be a rational number, output the result modulo 998244353.

Note: All formulas must be written in \(\LaTeX\) format. The input probabilities are given in percentages.

inputFormat

The first line contains three integers: n m k (n is the number of vertices, m is the number of edges, and k is the exponent used in the weight calculation).

The following m lines each contain two integers u v representing an edge between vertices u and v (1-indexed).

The last line contains n integers: p1 p2 ... pn where p_i is the percentage probability that the i-th vertex is colored black.

outputFormat

Output one integer: the expected weight of the black‐white graph modulo 998244353.

sample

3 2 1
1 2
2 3
50 50 50

499122178