Problem Description
Professor Zhang has an undirected graph G with n vertices and m edges. Each vertex is attached with a weight wi. Let Gi be the graph after deleting the i-th vertex from graph G. Professor Zhang wants to find the weight of G1,G2,...,Gn.
The weight of a graph G is defined as follows:
A connected component of an undirected graph G is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in G.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (2≤n≤105,1≤m≤2×105) -- the number of vertices and the number of edges.
The second line contains n integers w1,w2,...,wn (1≤wi≤109), denoting the weight of each vertex.
In the next m lines, each contains two integers xi and yi (1≤xi,yi≤n,xi≠yi), denoting an undirected edge.
There are at most 1000 test cases and ∑n,∑m≤1.5×106.
Output
For each test case, output an integer S=(∑i=1ni⋅zi) mod (109+7), where zi is the weight of Gi.
Sample Input
1
3 2
1 2 3
1 2
2 3
Sample Output
20