Zhang 教授有一个包含 $n$ 个顶点和 $m$ 条边的无向图 $G$。每个顶点都有一个整数权值 $w_i$。令 $G_i$ 为从图 $G$ 中删除第 $i$ 个顶点后得到的图。Zhang 教授想要计算 $G_1, G_2, \dots, G_n$ 的权值。

图 $G$ 的权值定义如下：

• 如果 $G$ 是连通的，则 $G$ 的权值为 $G$ 中每个顶点的权值之积。
• 否则，$G$ 的权值为 $G$ 中所有连通分量的权值之和。

无向图 $G$ 的连通分量 $H$ 是一个子图，其中任意两个顶点都通过路径相连，且 $G$ 中没有其他顶点通过路径与 $H$ 中的任何顶点相连。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5$)，分别表示顶点数和边数。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$)，表示每个顶点的权值。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$)，表示一条无向边。

测试数据最多有 1000 组，所有测试数据的 $n$ 之和不超过 $1.5 \cdot 10^6$，所有测试数据的 $m$ 之和也不超过 $1.5 \cdot 10^6$。

输出格式

对于每组测试数据，输出整数 $S = (\sum_{i=1}^{n} i \cdot z_i) \pmod{10^9 + 7}$，其中 $z_i$ 是 $G_i$ 的权值。

样例

样例输入 1

1
3 2
1 2 3
1 2
2 3

样例输出 1

20