配点 : $600$ 点

問題文

$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)$ で出力してください。

注記

有理数を出力する際は、まずその有理数を分数 $\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$
• 与えられるグラフは単純
• 入力に含まれる値は全て整数である

入力

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

$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)$ で出力せよ。

3 2 1
3 1 5
1 2
1 3

3
500000005
500000008

• 唯一の操作で辺 $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$ となります。

3 2 2
12 48 36
1 2
1 3

750000036
36
250000031

• $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}$ となります。

4 5 1000
578 173 489 910
1 2
2 3
3 4
4 1
1 3

201113830
45921509
67803140
685163678