K. Middle Point Graph
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a simple connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges.

For each vertex, we assign it a random point $$$(x_i,y_i,z_i)$$$, where $$$x_i,y_i,z_i$$$ are independent uniform random real numbers in $$$[0,1]$$$.

For each edge, its coordinate is defined as the middle point of its two ends' coordinates. The middle point of $$$(a, b, c)$$$ and $$$(x, y, z)$$$ is $$$(\frac{a + x}{2}, \frac{b + y}{2}, \frac{c + z}{2})$$$.

Among these $$$n + m$$$ points, you are to find the expected number of ways to choose $$$4$$$ coplanar distinct points. Print the answer modulo $$$10^9+7$$$.

Input

The first line contains a positive integer $$$T$$$ ($$$1\le T\le 10^4$$$), denoting the number of test cases.

For each testcase:

  • The first line contains two integers $$$n, m$$$, ($$$1\le n\le 2\cdot 10^5, n - 1\le m\le 5\cdot 10^5$$$) denoting the number of vertices and edges.
  • The next $$$m$$$ lines each contains two integers $$$u, v$$$ ($$$1\le u,v\le n$$$), denoting an edge connecting $$$u$$$ and $$$v$$$.

It is guaranteed that $$$\sum n\le 2\cdot 10^5$$$, $$$\sum m\le 5\cdot 10^5$$$.

An empty line is placed before each testcase for better readability.

Output

For each testcase, output one line containing a single integer denoting the answer module $$$10^9+7$$$.

Example
Input
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
Output
593
88
0