410577: GYM104053 K Middle Point Graph
Description
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$$$.
InputThe 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.
OutputFor each testcase, output one line containing a single integer denoting the answer module $$$10^9+7$$$.
ExampleInput3Output
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