410577: GYM104053 K Middle Point Graph

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$$$.

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.

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

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

593
88
0