Description

一张 n 个点 m 条边的无向图，可能有重边，但没有自环。点的编号为 1 ~ n。点 i 的权值为 $W_i$。

小明首先空降到一个点 x。到达点 x 的概率为 $D_x/(2·m)$，其中 $D_x$ 表示点 x 的度数。然后小明又走了 k 步，每步操作如下：

• 随机选择当前所在点的一条邻接边，到达另一个端点（记为 y），得分为该端点的权值 $W_y$。这里的随机选择是指在所有邻接边中等概率地选择。

每步操作的得分之和为总得分。

问：小明期望总得分是多少？假设答案可以表示成 A/B（A 和 B 均为整数，且互质）的形式，你只需要输出 A/B mod (10^9+7) 的值。

Input

第一行：三个整数 n, m, k

第二行：n 个整数 $W_i$

接下来 m 行：每行两个整数 x, y，表示 x 和 y 之间有一条边。

Output

一个整数，表示答案 mod (10^9+7)

Sample Input

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

Sample Output

750000011

Sample Hint

23/4 mod (10^9+7) = 750000011。

Data Size

1 ≤ n, k ≤ 10^5, 1 ≤ m ≤ 2×10^5, 1 ≤ w_i ≤ 100, 1 ≤ x, y ≤ n, x ≠ y。