题目描述

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

题目大意

给定一张 $n$ 个点 $m$ 条边的无向图，节点从 $1\sim n$ 编号，每个节点 $i$ 都有点权 $a_i$。接下来要进行如下操作：

• 从 $m$ 条边中等概率地选择一条，将其两个端点 $u,v$ 的点权 $a_u,a_v$ 修改为他们的算术平均值 $\dfrac{a_u+a_v}2$。

求 $k$ 次操作后每个点点权的期望。

—— by Register_int

3 2 1
3 1 5
1 2
1 3

3
500000005
500000008

3 2 2
12 48 36
1 2
1 3

750000036
36
250000031

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

201113830
45921509
67803140
685163678

提示

注記

有理数を出力する際は、まずその有理数を分数 $\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} $ となります。