Fantasia

장 교수는 정점 $n$개와 간선 $m$개를 가진 무방향 그래프 $G$를 가지고 있다. 각 정점에는 정수 가중치 $w_i$가 있다. 그래프 $G$에서 $i$번째 정점을 삭제해 얻은 그래프를 $G_i$라고 하자. 장 교수는 $G_1, G_2, \ldots, G_n$의 가중치를 구하려고 한다.

그래프 $G$의 가중치는 다음과 같이 정의된다.

• $G$가 연결되어 있으면, $G$의 가중치는 $G$에 있는 각 정점 가중치의 곱이다.
• 그렇지 않으면, $G$의 가중치는 $G$의 모든 연결 요소 가중치의 합이다.

무방향 그래프 $G$의 연결 요소 $H$는 다음을 만족하는 부분 그래프이다. $H$ 안의 임의의 두 정점은 경로로 연결되며, $G$의 다른 정점 중 $H$의 어떤 정점과도 경로로 연결되는 정점은 없다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 10^5$, $1 \le m \le 2 \cdot 10^5$). $n$은 정점의 수, $m$은 간선의 수이다.

둘째 줄에는 $n$개의 정수 $w_1, w_2, \ldots, w_n$이 주어진다 ($1 \le w_i \le 10^9$). $w_i$는 각 정점의 가중치이다.

다음 $m$개의 줄에는 각각 두 정수 $x_i$와 $y_i$가 주어진다 ($1 \le x_i, y_i \le n$, $x_i \ne y_i$). 이는 무방향 간선을 나타낸다.

테스트 케이스는 최대 $1000$개이며, 모든 테스트 케이스에서 $n$의 합은 최대 $1.5 \cdot 10^6$, $m$의 합도 최대 $1.5 \cdot 10^6$이다.

각 테스트 케이스마다 정수 $S = (\sum\limits_{i = 1}^{n}{i \cdot z_i})$를 $10^9 + 7$로 나눈 나머지를 출력한다. 여기서 $z_i$는 $G_i$의 가중치이다.