Fantasia

Problem Description

Professor Zhang has an undirected graph $G$ with $n$ vertices and $m$ edges. Each vertex is attached with a weight $w_i$. Let $G_i$ be the graph after deleting the $i$-th vertex from graph $G$. Professor Zhang wants to find the weight of $G_1, G_2, ..., G_n$. The weight of a graph $G$ is defined as follows:

1. If $G$ is connected, then the weight of $G$ is the product of the weight of each vertex in $G$.
2. Otherwise, the weight of $G$ is the sum of the weight of all the connected components of $G$. 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 \le n \le 10^5, 1 \le m \le 2 \times 10^5)$ -- the number of vertices and the number of edges. The second line contains $n$ integers $w_1, w_2, ..., w_n$ $(1 \le w_i \le 10^9)$, denoting the weight of each vertex. In the next m lines, each contains two integers $x_i$ and $y_i$ $(1 \le x_i, y_i \le n, x_i \ne y_i)$, denoting an undirected edge. There are at most $1000$ test cases and $\sum n, \sum m \le 1.5 \times 10^6$.

Output

For each test case, output an integer $S = (\sum\limits_{i=1}^{n}i\cdot z_i) \text{ mod } (10^9 + 7)$, where $z_i$ is the weight of $G_i$.

Sample Input

1
3 2
1 2 3
1 2
2 3

Sample Output

20

Author

zimpha

Source

2016 Multi-University Training Contest 2