Allen, Nella's older brother, has a better way of building graphs; he plugs them into his graph generator! The generator takes $3$ items as input:

1. An initial graph $G$ consisting of $N$ nodes labeled from $1$ to $N$ connected by $M$ distinct undirected edges of length $1$.
2. An array $P$ of length $N$, where $P_i=1$ if nodes labeled $i$ are producers and $P_i=0$ otherwise.
3. A positive integer $K$, the number of generation phases.

The generator then begins building the graph, happening in $K$ generation phases. In the first phase, the graph $G$ is constructed. Then, for every phase after the first, the generator does the following:

For every node $u$ that is a producer constructed in the previous phase, construct a copy of $G$ and connect node $1$ of the copy to $u$ with an undirected edge of length $1$.

To estimate the size of the graph constructed after the $K$-th generation phase is over, compute the sum of the lengths of the shortest paths between every pair of nodes.

Constraints

$1\le N\le 3\times {10}^3$

$0\le M\le 3\times {10}^3$

$1\le K\le {10}^6$

$P_i\in \{0,1\}$

$1\le u_j,v_j\le N$

$G$ is connected.

$\sum _{i=1}^N{P}_i\ge 1$

Subtask 1 [20%]

$\sum _{i=1}^N{P}_i=1$

Subtask 2 [30%]

$M=\frac{N(N-1)}{2}$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains $3$ integers $N$, $M$, and $K$.

The second line contains $N$ integers $P_1,P_2,\dots ,P_N$.

The next $M$ lines each contain $2$ integers $u_j$ and $v_j$, the labels of the endpoints of the $j$-th edge in $G$. All edges are distinct, and there are no self-loops.

Output Specification

Output the sum of the lengths of the shortest paths between every pair of nodes. Since this value may be large, output it modulo ${10}^9+7$.

Sample Input

2 1 2
1 1
1 2

Sample Output

35