CF446D.DZY Loves Games

Today DZY begins to play an old game. In this game, he is in a big maze with n rooms connected by m corridors (each corridor allows to move in both directions). You can assume that all the rooms are connected with corridors directly or indirectly.

DZY has got lost in the maze. Currently he is in the first room and has k lives. He will act like the follows:

• Firstly he will randomly pick one of the corridors going from his current room. Each outgoing corridor has the same probability to be picked.
• Then he will go through the corridor and then the process repeats.

There are some rooms which have traps in them. The first room definitely has no trap, the n-th room definitely has a trap. Each time DZY enters one of these rooms, he will lost one life. Now, DZY knows that if he enters the n-th room with exactly 2 lives, firstly he will lost one live, but then he will open a bonus round. He wants to know the probability for him to open the bonus round. Please, help him.

今天，DZY 开始玩一个古老的游戏。在这个游戏中，他身处一座拥有 $n$ 个房间的大迷宫中，这些房间由 $m$ 条走廊连接（每条走廊允许双向通行）。你可以假设所有房间均通过走廊直接或间接连通。

DZY 在迷宫中迷路了。目前他位于第 $1$ 个房间，并拥有 $k$ 条生命。他的行动规则如下：

• 首先，他将从当前房间出发的走廊中随机选择一条。每条出边走廊被选中的概率相等。
• 然后，他穿过该走廊到达下一个房间，之后重复上述过程。

其中一些房间设有陷阱。第 $1$ 个房间一定没有陷阱，第 $n$ 个房间一定有陷阱。每次 DZY 进入一个有陷阱的房间，他就会损失一条生命。现在，DZY 已知：若他恰好以 2 条生命的状态进入第 $n$ 个房间，则他首先会损失 1 条生命，但随后将开启一个奖励关卡。他想知道开启该奖励关卡的概率。请帮助他。

The first line contains three integers n, m, k (2 ≤ n ≤ 500; 1 ≤ m ≤ 105; 2 ≤ k ≤ 109).

The second line contains n integers, each of them is either 0 or 1. If the i-th number is 1, then the i-th room has a trap, otherwise it has not a trap. Please note, that the number of rooms with a trap is no more than 101. It is guaranteed that the first room has no trap, and the n-th room has a trap.

Then m lines follows. Each of them contains two integers u__i, v__i (1 ≤ u__i, v__i ≤ n; u__i ≠ v__i), meaning that current corridor connects two rooms u__i and v__i. It is guaranteed that the corridor system is connected.

第一行包含三个整数 $n$、$m$、$k$（$2 \le n \le 500$；$1 \le m \le 10^5$；$2 \le k \le 10^9$）。

第二行包含 $n$ 个整数，每个数为 $0$ 或 $1$。若第 $i$ 个数为 $1$，则第 $i$ 个房间设有陷阱；否则没有陷阱。注意：设有陷阱的房间总数不超过 $101$。保证第 $1$ 个房间没有陷阱，且第 $n$ 个房间有陷阱。

接下来是 $m$ 行，每行包含两个整数 $u_i$、$v_i$（$1 \le u_i, v_i \le n$；$u_i \ne v_i$），表示当前走廊连接房间 $u_i$ 和 $v_i$。保证走廊系统是连通的。

Print the only real number — the probability for DZY to open the bonus round. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

输出唯一的实数——DZY 开启奖励关卡的概率。若答案的相对误差或绝对误差不超过 $10^{-4}$，则视为正确。