AT_abc277_g [ABC277G] Random Walk to Millionaire

[problemUrl]: https://atcoder.jp/contests/abc277/tasks/abc277_g $ 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 $

答えを出力せよ。

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