题目描述

$N$ 個の頂点と $M$ 本の辺からなる連結かつ単純な無向グラフが与えられます。
$i\ =\ 1,\ 2,\ \ldots,\ M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。

高橋君は、はじめレベルが $0$ の状態で頂点 $1$ におり、下記の行動をちょうど $K$ 回行います。

• まず、いまいる頂点に隣接する頂点の中から、$1$ つを等確率でランダムに選択し、その頂点に移動する。
• その後、移動後の頂点 $v$ に応じて、下記のイベントが発生します。
  • $C_v\ =\ 0$ のとき : 高橋君のレベルが $1$ だけ増加する。
  • $C_v\ =\ 1$ のとき : 高橋君のいまのレベルを $X$ とする。高橋君は $X^2$ 円のお金を獲得する。

上記の $K$ 回の行動の過程で高橋君が獲得するお金の合計金額の期待値を $\mathrm{mod}\,\ 998244353$ で出力してください（注記参照）。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给出一个 $n$ 个点 $m$ 条边的无向简单连通图，每个点有一个点权 $C_i\in\{0,1\}$。

$\text{Takahashi}$ 初始时在 $1$ 号点，等级为 $0$。接下来他要做 $K$ 次如下操作：

• 随机地走向当前所在点的一个相邻点。
• 如果这个点 $C_i=0$，将等级加一；如果这个点 $C_i=1$，设 $\text{Takahashi}$ 当前的等级为 $X$，他可以获得 $X^2$ 元钱。

求 $K$ 次操作中 $\text{Takahashi}$ 一共获得的钱数的期望，答案对 $998244353$ 取模。

$(1\le n,m,K\le 3000)$

5 4 8
4 5
2 3
2 4
1 2
0 0 1 1 0

89349064

8 12 20
7 6
2 6
6 4
2 1
8 5
7 2
7 5
3 7
3 5
1 8
6 3
1 4
0 0 1 1 0 0 0 0

139119094

提示

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、$R\ \times\ Q\ \equiv\ P\pmod{998244353}$ かつ $0\ \leq\ R\ \lt\ 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $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 $
• 与えられるグラフは連結
• $C_i\ \in\ \lbrace\ 0,\ 1\rbrace$
• 入力はすべて整数

Sample Explanation 1

高橋君の移動経路として考えられるものは複数ありますが、ここでは例として、高橋君が頂点 $1$ を始点として、$ 1\ \rightarrow\ 2\ \rightarrow\ 4\ \rightarrow\ 5\ \rightarrow\ 4\ \rightarrow\ 2\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 3 $ と移動する場合に獲得するお金の合計金額を計算します。 1. 高橋君は $1$ 回目の行動で、いまいる頂点 $1$ に隣接する頂点 $2$ に移動します。$C_2\ =\ 0$ であるため、その後高橋君のレベルが $1$ に上がります。 2. 高橋君は $2$ 回目の行動で、いまいる頂点 $2$ に隣接する頂点 $4$ に移動します。$C_4\ =\ 1$ であるため、その後高橋君は $1^2\ =\ 1$ 円を獲得します。 3. 高橋君は $3$ 回目の行動で、いまいる頂点 $4$ に隣接する頂点 $5$ に移動します。$C_5\ =\ 0$ であるため、その後高橋君のレベルが $2$ に上がります。 4. 高橋君は $4$ 回目の行動で、いまいる頂点 $5$ に隣接する頂点 $4$ に移動します。$C_4\ =\ 1$ であるため、その後高橋君は $2^2\ =\ 4$ 円を獲得します。 5. 高橋君は $5$ 回目の行動で、いまいる頂点 $4$ に隣接する頂点 $2$ に移動します。$C_2\ =\ 0$ であるため、その後高橋君のレベルが $3$ に上がります。 6. 高橋君は $6$ 回目の行動で、いまいる頂点 $2$ に隣接する頂点 $1$ に移動します。$C_1\ =\ 0$ であるため、その後高橋君のレベルが $4$ に上がります。 7. 高橋君は $7$ 回目の行動で、いまいる頂点 $1$ に隣接する頂点 $2$ に移動します。$C_2\ =\ 0$ であるため、その後高橋君のレベルが $5$ に上がります。 8. 高橋君は $8$ 回目の行動で、いまいる頂点 $2$ に隣接する頂点 $3$ に移動します。$C_3\ =\ 1$ であるため、その後高橋君は $5^2\ =\ 25$ 円を獲得します。 よって、高橋君が獲得するお金の合計金額は、$1\ +\ 4\ +\ 25\ =\ 30$ 円です。