Problem E
Cursed Vault

H’Arrry, Rrron, and Anemone have found a vault of treasure! But unfortunately for them, the vault is cursed. Once they open the vault, the vault begins duplicating the treasure held within over the course of $T$ time steps.

Specifically, the vault is separated into $N$ locations $0, 1 , \dots , n-1$, each location starting with $1$ treasure in it at $t=0$ when the vault is opened. Each location is also connected to some number of other locations.

The vault will duplicate treasure over $T$ time steps (until $t = T$), and treasure in different locations are duplicated in different ways.

After each time step $t$, each location $i$ will add treasure at the next time step in one of two ways:

1. Adds a single treasure to every location it’s connected to.

2. Adds $k_{i, t}$ treasure to every location it’s connected to where $k_{i, t}$ is the current amount of treasure in the location.

Locations do not add treasure to themselves, and the amount of treasure to be added at the next time step $t+1$ is determined by the amount of treasure in the location at the current time step $t$.

Calculate the sum of all treasure contained in all locations in the vault at time $t = T$ (where $T$ time steps have passed). Because this number may be very large, output the answer modulo $10^9 + 7$.

Input

The first line of input contains three integers $N$, $M$, and $T$ ($2 \leq N \leq 50$, $1 \leq M \leq \frac{N(N-1)}{2}$, $1 \leq T \leq 10^{12}$), the number of locations, the number of connections, and the number of time steps.
The next $N$ lines each contain a single integer 1 or 2, where the $i$th line indicates the way that $i-1$th location duplicates treasure (either the 1st way or the 2nd way).
The next $M$ lines each contain two integers $u$ and $v$ ($0 \leq u, v \leq N-1$, $u < v$), indicating that location $u$ is connected to location $v$ and location $v$ is connected to location $u$. The same connection will not appear twice in the input.

Output

Output the total amount of treasure in the vault after $T$ time steps, modulo $10^9 + 7$.

2 1 2
1
2
0 1

7

4 4 3
1
2
2
1
0 1
1 2
2 3
1 3

79