#5091. [Lydsy1711月赛]摘苹果

内存限制:256 MiB 时间限制:1 Sec

题目描述

小Q的工作是采摘花园里的苹果。在花园中有n棵苹果树以及m条双向道路,苹果树编号依次为1到n,每条道路的两
端连接着两棵不同的苹果树。假设第i棵苹果树连接着d_i条道路。小Q将会按照以下方式去采摘苹果:
1.小Q随机移动到一棵苹果树下,移动到第i棵苹果树下的概率为d_i/(2m),但不在此采摘。
2.等概率随机选择一条与当前苹果树相连的一条道路,移动到另一棵苹果树下。
3.假设当前位于第i棵苹果树下,则他会采摘a_i个苹果,多次经过同一棵苹果树下会重复采摘。
4.重复第2和3步k次。
请写一个程序帮助计算小Q期望摘到多少苹果。

输入格式

第一行包含三个正整数n,m,k(n,k<=100000,m<=200000),分别表示苹果树和道路的数量以及重复步骤的次数。

第二行包含n个正整数,依次表示a_1,a_2,...,a_n(1<=a_i<=100)。
接下来m行,每行两个正整数u,v(1<=u,v<=n,u!=v),表示第u和第v棵苹果树之间存在一条道路。

输出格式

 若答案为P/Q,则输出一行一个整数,即P*Q^{-1} mod 1000000007(10^9+7)。

样例

样例输入


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

样例输出


			
750000011
//期望为5.75=23/4=(23*250000002) mod 1000000007=750000011。

数据范围与提示