Sum of Distances

문제

Bessie has a collection of connected, undirected graphs $G_1,G_2,\dots ,G_{K}G\_1,G\_2,\backslash ldots,G\_K$ ($2\le K\le 5\cdot {10}^{4}2\backslash le\; K\backslash le\; 5\backslash cdot\; 10^4$). For each $1\le i\le K1\backslash le\; i\backslash le\; K$, $G_{i}G\_i$ has exactly $N_{i}N\_i$ ($N_i\ge 2N\_i\backslash ge\; 2$) vertices labeled $1\dots N_{i}1\backslash ldots\; N\_i$ and $M_{i}M\_i$ ($M_i\ge N_i-1M\_i\backslash ge\; N\_i-1$) edges. Each $G_{i}G\_i$ may contain self-loops, but not multiple edges between the same pair of vertices.

Now Elsie creates a new undirected graph $GG$ with $N_1\cdot N_2\cdots N_{K}N\_1\backslash cdot\; N\_2\backslash cdots\; N\_K$ vertices, each labeled by a $KK$-tuple $(j_1,j_2,\dots ,j_K)(j\_1,j\_2,\backslash ldots,j\_K)$ where $1\le j_i\le N_{i}1\backslash le\; j\_i\backslash le\; N\_i$. In $GG$, two vertices $(j_1,j_2,\dots ,j_K)(j\_1,j\_2,\backslash ldots,j\_K)$ and $(k_1,k_2,\dots ,k_K)(k\_1,k\_2,\backslash ldots,k\_K)$ are connected by an edge if for all $1\le i\le K1\backslash le\; i\backslash le\; K$, $j_{i}j\_i$ and $k_{i}k\_i$ are connected by an edge in $G_{i}G\_i$.

Define the distance between two vertices in $GG$ that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex $(1,1,\dots ,1)(1,1,\backslash ldots,1)$ and every vertex in the same component as it in $GG$, modulo ${10}^9+710^9+7$.

입력

The first line contains $KK$, the number of graphs.

Each graph description starts with $N_{i}N\_i$ and $M_{i}M\_i$ on a single line, followed by $M_{i}M\_i$ edges.

Consecutive graphs are separated by newlines for readability. It is guaranteed that $\sum N_i\le {10}^5\backslash sum\; N\_i\backslash le\; 10^5$ and $\sum M_i\le 2\cdot {10}^5\backslash sum\; M\_i\backslash le\; 2\backslash cdot\; 10^5$.

출력

The sum of the distances between vertex $(1,1,\dots ,1)(1,1,\backslash ldots,1)$ and every vertex that is reachable from it, modulo ${10}^9+710^9+7$.

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

4

3

4 4
1 2
2 3
3 1
3 4

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

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

706