AT_abc199_f [ABC199F] Graph Smoothing

有一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。 第 $i$ 条边连接顶点 $X_i$ 和顶点 $Y_i$。此外，顶点 $i$ 上最初写有整数 $A_i$。 你需要进行 $K$ 次如下操作： - 从 $M$ 条边中，等概率且相互独立地随机选择一条边。记该边连接的两个顶点上写的数的平均值为 $x$，然后将这两个顶点上的数都替换为 $x$。 请你求出每个顶点 $i$ 在 $K$ 次操作后所写数字的期望值，并按照注释中的要求对 $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$ > $\vdots$ > $X_M$ $Y_M$

请输出 $N$ 行。 第 $i$ 行输出第 $i$ 个顶点在 $K$ 次操作后所写数字的期望值，按照注释中的要求对 $10^9+7$ 取模输出。

### 注释 输出有理数时，首先将其表示为分数 $\frac{y}{x}$，其中 $x, y$ 为整数，且 $x$ 不能被 $10^9+7$ 整除（在本题的约束下总能做到）。 然后，输出唯一满足 $0 \leq z \leq 10^9+6$ 且 $xz \equiv y \pmod{10^9+7}$ 的整数 $z$。 ### 约束条件 - $2 \leq N \leq 100$ - $1 \leq M \leq \frac{N(N-1)}{2}$ - $0 \leq K \leq 10^9$ - $0 \leq A_i \leq 10^9$ - $1 \leq X_i \leq N$ - $1 \leq Y_i \leq N$ - 给定的图是简单图 - 输入中的所有值均为整数 ### 样例解释 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}$。 将其按注释中的方式转化为 $10^9+7$ 下的表达，分别为 $3, 500000005, 500000008$。 ### 样例解释 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}$。 由 ChatGPT 4.1 翻译