問題文

$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$ で出力してください（注記参照）。

注記

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

出力

答えを出力せよ。

入力例 1

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

出力例 1

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$ 円です。

入力例 2

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

出力例 2

139119094