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