Today, you and your friends are going to hit up Khan el-Khalili, Cairo, a famous bazaar founded in the late 14th century. It's still going strong today, with many luxuries to buy and foods to eat.

In the bazaar, there are ~n~ vendors, numbered from ~1~ to ~n~, connected by ~m~ paths. Beginning at vendor ~1~, you and your friends will perform the following operation ~L~ times:

1. Buy something from the current vendor.
2. Optionally, move to any vendor connected to your current vendor by a path.

Once your shopping is finished, you'll be too tired to continue, and drop to the ground. Some vendors have benches where customers can rest. If you end your trip at a vendor with a bench, you can take a break, and the trip is considered successful. Otherwise, the trip is considered a failure.

You start to wonder: how many unique sequences of vendors can you buy stuff from, that results in a successful trip?

Input

The first line contains an three integers ~n~ (~1 \leq n \leq 100~), ~m~ (~0 \leq m \leq 500~), ~L~ (~1 \leq L \leq 10^{18}~), the number of vendors in the bazaar, the number of paths connecting them, and the number of operations you will perform.

The next line contains ~n~ integers ~b_1 \dots b_n~ (~0 \leq b_i \leq 1~). ~b_i = 1~ if the ~i~th vendor has a bench, and ~0~ otherwise.

The next ~m~ lines are in the form \(x \: y\) (~1 \leq L, R \leq n~), indicating that there is a path between vendors ~x~ and ~y~.

Each vendor has at most ~5~ paths coming from it.

Output

Output the number of unique sequences of vendors you can visit, while ending your trip at a vendor with a bench. Since this value may be very large, output it modulo ~10^9 + 7~.

Note

You should use Pypy3 for your Python submissions.

Example

Input 1

5 6 2
0 0 1 1 0
1 2
1 3
1 4
1 5
2 3
3 4

Output 1

7

There are ~7~ ways to traverse the bazaar, starting from vendor ~1~ and ending on a vendor with a bench (either vendor ~3~ or ~4~). Note that:

• You are allowed to stay at your current position during an operation.
• Staying at ~1~ and going to ~4~ (~1~, ~1~, ~4~) is considered distinct from going to ~4~, then staying there (~1~, ~4~, ~4~).

Input 2

5 6 3
0 0 1 1 0
1 2
1 3
1 4
1 5
2 3
3 4

Output 2

27

Adding more operations makes the number of moves exponentially larger.

Input 4

8 10 1000000000000000000
1 0 1 0 1 1 1 1
1 2
2 3
2 4
2 5
3 5
3 8
4 6
5 6
6 7
7 8

Output 4

277821039