图论算法大师绝不会容忍任何不连通的子图。 美学家只会将边导出子图视为必要的子图。 强迫症患者总是会从给定的简单无向图中随机选择一个子图。

这就是为什么 Picard 要求你计算：从给定的简单无向图中等概率地随机选择四条不同的边，使得这四条边构成的边导出子图是连通的概率。这里我们称图中的一个边子集以及所有作为这些边端点的顶点所构成的图为边导出子图。

为了避免精度问题，Picard 将该概率记为 $p$，将总边数记为 $m$，你需要输出 $(p \cdot \binom{m}{4}) \pmod{10^9 + 7}$ 的值。容易证明 $p \cdot \binom{m}{4}$ 是一个整数。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，其中 $T \le 10$。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，分别表示给定简单无向图的顶点数和边数，其中 $4 \le n \le 10^5$ 且 $4 \le m \le 2 \times 10^5$。

接下来的 $m$ 行描述图中的所有边，第 $i$ 行包含两个整数 $u$ 和 $v$，表示连接第 $u$ 个顶点和第 $v$ 个顶点的一条边，其中 $1 \le u, v \le n$ 且 $u \neq v$。

保证给定的图不包含自环或重边。

输出格式

对于每组测试数据，输出一行，包含一个整数，对应于 $(p \cdot \binom{m}{4}) \pmod{10^9 + 7}$ 的值，其中 $p$ 表示你被要求计算的概率。

样例

样例输入 1

2
4 4
1 2
2 3
3 4
4 1
4 6
1 2
1 3
1 4
2 3
2 4
3 4

样例输出 1

1
15