配点 : $600$ 点

問題文

$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$ 円のお金を獲得する。
• $C_v = 0$ のとき : 高橋君のレベルが $1$ だけ増加する。
• $C_v = 1$ のとき : 高橋君のいまのレベルを $X$ とする。高橋君は $X^2$ 円のお金を獲得する。

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

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $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$
• 入力はすべて整数

入力

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

$N$ $M$ $K$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$C_1$ $C_2$ $\ldots$ $C_N$

出力

答えを出力せよ。

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

89349064

高橋君の移動経路として考えられるものは複数ありますが、ここでは例として、高橋君が頂点 $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$ 円です。

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