问题描述

我们有一个简单的无向图，有 $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)$ 取模后的结果，按照注释中的要求打印。

示例输入 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}$。 按照注释中的要求对 $(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$。

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