Problem Statement

We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$ and the edges are numbered $1$ through $M$. Edge $i$ connects Vertex $X_i$ and Vertex $Y_i$. Initially, Vertex $i$ has an integer $A_i$ written on it. You will do the following operation $K$ times:

• Choose one from the $M$ edges uniformly at random and independently from other choices. Let $x$ be the arithmetic mean of the numbers written on the two vertices connected by that edge. Replace each number written on those vertices with $x$.

For each vertex $i$, find the expected value of the number written on that vertex after $K$ operations, and print it modulo $(10^9 + 7)$ as described in Notes.

Note

When printing a rational number, first, represent it as a fraction $\frac{y}{x}$, where $x$ and $y$ are integers and $x$ is not divisible by $(10^9+7)$ (under the Constraints of this problem, such a representation is always possible). Then, print the only integer $z$ between $0$ and $(10^9+6)$ (inclusive) such that $xz \equiv y \pmod {10^9+7}$.

Constraints

• $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$
• The given graph is simple.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $N$ lines. The $i$-th line should contain the expected value of the number written on that vertex after $K$ operations, modulo $(10^9 + 7)$, as described in Notes.