F - 图形加平滑

得分：600分

题目描述

我们有一个简单无向图，具有$N$个顶点和$M$条边。顶点从$1$到$N$编号，边从$1$到$M$编号。
第$i$条边连接了顶点$X_i$和顶点$Y_i$。最开始，顶点$i$上有一个整数$A_i$。
你需要进行以下操作$K$次：

• 等概率且独立地选择$M$条边中的一条。令$x$为连接该边两个顶点的数字的算术平均数。将这两个顶点上的数字替换为$x$。

对于每个顶点$i$，计算在进行$K$次操作后顶点上的数字的期望值，并按照说明打印它对$(10^9 + 7)$取模的结果。

说明

当打印一个有理数时，首先表示它为$\frac{y}{x}$的形式，其中$x$和$y$是整数，$x$不能被$(10^9+7)$整除（根据这个问题的约束，这样的表示法总是存在的）。
然后，打印一个处于$0$到$(10^9+6)$之间的整数$z$，满足$xz \equiv y \pmod {10^9+7}$。

约束

• $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$次操作后顶点上的数字的期望值，对$(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}$。
如果按照说明将它们对$(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$。

这四种情况发生的概率都是$\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