問題文

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

入力例 1

3 2 1
3 1 5
1 2
1 3

出力例 1

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

入力例 2

3 2 2
12 48 36
1 2
1 3

出力例 2

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

入力例 3

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

出力例 3

201113830
45921509
67803140
685163678