给定一个包含 $n$ 个顶点和 $m$ 条边的简单连通无向图。

对于每个顶点，我们为其分配一个随机点 $(x_i, y_i, z_i)$，其中 $x_i, y_i, z_i$ 是在 $[0, 1]$ 区间内相互独立的均匀分布随机实数。

对于每条边，其坐标定义为该边两个端点坐标的中点。点 $(a, b, c)$ 和 $(x, y, z)$ 的中点为 $(\frac{a+x}{2}, \frac{b+y}{2}, \frac{c+z}{2})$。

在这 $n + m$ 个点中，求选出 4 个共面且互不相同的点的期望方案数。请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例： 第一行包含两个整数 $n, m$ ($1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 5 \cdot 10^5$)，分别表示顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示连接 $u$ 和 $v$ 的一条边。

保证 $\sum n \le 2 \cdot 10^5, \sum m \le 5 \cdot 10^5$。

每个测试用例前均有一个空行，以提高可读性。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3
7 18
2 1
2 3
3 4
2 5
6 4
7 5
6 5
3 1
1 5
1 7
7 3
2 6
2 7
4 5
5 3
4 2
6 7
6 3
5 7
1 2
2 3
4 2
5 1
1 4
3 5
3 1
1 0

样例输出 1

593
88
0