Problem Statement

You are given a connected simple undirected graph consisting of $N$ vertices and $M$ edges. For $i = 1, 2, \ldots, M$, the $i$-th edge connects vertex $u_i$ and vertex $v_i$.

Takahashi starts at Level $0$ on vertex $1$, and will perform the following action exactly $K$ times.

• First, choose one of the vertices adjacent to the vertex he is currently on, uniformly at random, and move to the chosen vertex.
• Then, the following happens according to the vertex $v$ he has moved to.
• If $C_v = 0$: Takahashi's Level increases by $1$.
  • If $C_v = 1$: Takahashi receives a money of $X^2$ yen, where $X$ is his current Level.

Print the expected value of the total amount of money Takahashi receives during the $K$ actions above, modulo $998244353$ (see Notes).

Note

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, it can also be proved that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $2 \leq N \leq 3000$
• $N-1 \leq M \leq \min\lbrace N(N-1)/2, 3000\rbrace$
• $1 \leq K \leq 3000$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $i \neq j \implies \lbrace u_i, v_i\rbrace \neq \lbrace u_j, v_j \rbrace$
• The given graph is connected.
• $C_i \in \lbrace 0, 1\rbrace$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M
C_1 C_2 \ldots C_N

Output

Print the answer.