图的平滑操作

题目描述

有一个 $N$ 个顶点、$M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

边 $i$ 连接顶点 $X_i$ 和顶点 $Y_i$。此外，顶点 $i$ 最初写着整数 $A_i$。

你将执行以下操作 $K$ 次：

• 从 $M$ 条边中，均匀随机且与其他选择独立地选 $1$ 条边。设这条边连接的两个顶点上写的数的平均值为 $x$，将这两个顶点上写的数都替换为 $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$。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $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$
• 给定的图是简单的
• 输入中的值均为整数