19437번 - Fantasia 다국어

문제

Professor Zhang has an undirected graph $G$ with $n$ vertices and $m$ edges. Each vertex has an integer weight $w_i$. Let $G_i$ be the graph obtained by deleting the $i$-th vertex from graph $G$. Professor Zhang wants to find the weights of $G_1, G_2, \ldots, G_n$.

The weight of a graph $G$ is defined as follows:

• If $G$ is connected, then the weight of $G$ is the product of the weight of each vertex in $G$.
• Otherwise, the weight of $G$ is the sum of the weights of all the connected components of $G$.

A connected component $H$ of an undirected graph $G$ is a subgraph in which any two vertices are connected by a path, and no other vertex in $G$ is connected to any vertex from $H$ by a path.

입력

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 \cdot 10^5$): the number of vertices and the number of edges.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ (1ドル \le w_i \le 10^9$) denoting the weight of each vertex.

Each of the next $m$ lines 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, the sum of $n$ in all the test cases is at most 1ドル.5 \cdot 10^6,ドル and the sum of $m$ in all the test cases is also at most 1ドル.5 \cdot 10^6$.

출력

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

제한

힌트