Problem Description

度度熊专门研究过“动态传递闭包问题”，他有一万种让大家爆蛋的方法；但此刻，他只想出一道简简单单的题——至繁，归于至简。

度度熊有一张n个点m条边的**无向图**，第$i$个点的点权为$v_i$。

如果图上存在一条**路径**使得点$i$可以走到点$j$，则称$i,j$是**带劲**的，记$f(i,j)=1$；否则$f(i,j)=0$。显然有$f(i,j) = f(j,i)$。

度度熊想知道求出：
$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} f(i,j) \times \max(v_i, v_j) \times (v_i \& v_j)$

其中$\&$是C++中的and位运算符，如1&3=1, 2&3=2。

请将答案对$10^9+7$取模后输出。

Input

第一行一个数，表示数据组数$T$。

每组数据第一行两个整数$n,m$；第二行$n$个数表示$v_i$；接下来$m$行，每行两个数$u,v$，表示点$u$和点$v$之间有一条无向边。**可能有重边或自环。**

数据组数T=50，满足：

- $1 \le n,m \le 100000$
- $1 \le v_i \le 10^9$。

其中90%的数据满足$n,m \le 1000$。

Output

每组数据输出一行，每行仅包含一个数，表示带劲的and和。

1
5 5
3 9 4 8 9 
2 1
1 3
2 1
1 2
5 2

99