AT_abc199_f [ABC199F] Graph Smoothing

[problemUrl]: https://atcoder.jp/contests/abc199/tasks/abc199_f $ N $ 頂点 $ M $ 辺の単純無向グラフがあります。頂点には $ 1 $ から $ N $ までの、辺には $ 1 $ から $ M $ までの番号がついています。 辺 $ i $ は頂点 $ X_i $ と頂点 $ Y_i $ を結んでいます。また、頂点 $ i $ には最初整数 $ A_i $ が書かれています。 あなたは $ K $ 回にわたって以下の操作を行います。 - $ M $ 本ある辺の中から、一様ランダムかつ他の選択と独立に $ 1 $ 本選ぶ。その辺が結ぶ $ 2 $ 頂点に書かれている数の平均を $ x $ として、その $ 2 $ 頂点に書かれている数を両方 $ x $ で置き換える。 各頂点 $ i $ について、$ K $ 回の操作後に頂点 $ i $ に書かれている数の期待値を求め、注記の通り $ \bmod\ (10^9\ +\ 7) $ で出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ A_3 $ $ \dots $ $ A_N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ X_3 $ $ Y_3 $ $ \hspace{15pt}\ \vdots $ $ X_M $ $ Y_M $

$ N $ 行にわたって出力せよ。 $ i $ 行目には、$ K $ 回の操作後に頂点 $ i $ に書かれている数の期待値を、注記に従って $ \bmod\ (10^9\ +\ 7) $ で出力せよ。

### 注記 有理数を出力する際は、まずその有理数を分数 $ \frac{y}{x} $ として表してください。 ここで、$ x,y $ は整数であり、$ x $ は $ 10^9+7 $ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。 そして、$ xz\ \equiv\ y\ \pmod\ {10^9+7} $ を満たすような $ 0 $ 以上 $ 10^9+6 $ 以下の唯一の整数 $ z $ を出力してください。 ### 制約 - $ 2\ \le\ N\ \le\ 100 $ - $ 1\ \le\ M\ \le\ \frac{N(N\ -\ 1)}{2} $ - $ 0\ \le\ K\ \le\ 10^9 $ - $ 0\ \le\ A_i\ \le\ 10^9 $ - $ 1\ \le\ X_i\ \le\ N $ - $ 1\ \le\ Y_i\ \le\ N $ - 与えられるグラフは単純 - 入力に含まれる値は全て整数である ### Sample Explanation 1 \- 唯一の操作で辺 $ 1 $ が選ばれた場合 : 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 2,\ 2,\ 5 $ となります - 唯一の操作で辺 $ 2 $ が選ばれた場合 : 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 4,\ 1,\ 4 $ となります 従って、操作後に頂点 $ 1,\ 2,\ 3 $ に書かれている数の期待値はそれぞれ $ 3,\ \frac{3}{2},\ \frac{9}{2} $ となります。 これらを注記に従って $ \bmod\ (10^9\ +\ 7) $ の表現に変換すると、それぞれ $ 3,\ 500000005,\ 500000008 $ となります。 ### Sample Explanation 2 \- $ 1 $ 回目の操作で辺 $ 1 $ が選ばれた場合 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 30,\ 30,\ 36 $ となります - $ 2 $ 回目の操作で辺 $ 1 $ が選ばれた場合 : 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 30,\ 30,\ 36 $ となります - $ 2 $ 回目の操作で辺 $ 2 $ が選ばれた場合 : 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 33,\ 30,\ 33 $ となります - $ 1 $ 回目の操作で辺 $ 2 $ が選ばれた場合 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 24,\ 48,\ 24 $ となります - $ 2 $ 回目の操作で辺 $ 1 $ が選ばれた場合 : 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 36,\ 36,\ 24 $ となります - $ 2 $ 回目の操作で辺 $ 2 $ が選ばれた場合 : 頂点 $ 1,\ 2,\ 3 $ に書かれている数はそれぞれ $ 24,\ 48,\ 24 $ となります これら $ 4 $ 通りのケースが各 $ \frac{1}{4} $ の確率で起こるので、頂点 $ 1,\ 2,\ 3 $ に最終的に書かれている数の期待値はそれぞれ $ \frac{123}{4},\ \frac{144}{4}\ (=36),\ \frac{117}{4} $ となります。