Bessie has a collection of connected, undirected graphs $G_1,G_2,\ldots,G_K$
($2\le K\le 5\cdot 10^4$). For each $1\le i\le K$, $G_i$ has exactly $N_i$
($N_i\ge 2$) vertices labeled $1\ldots N_i$ and $M_i$ ($M_i\ge N_i-1$) edges.
Each $G_i$ may contain self-loops, but not multiple edges between the same pair
of vertices.

Now Elsie creates a new undirected graph $G$ with $N_1\cdot N_2\cdots N_K$
vertices, each labeled by a $K$-tuple $(j_1,j_2,\ldots,j_K)$ where
$1\le j_i\le N_i$. In $G$, two vertices $(j_1,j_2,\ldots,j_K)$ and
$(k_1,k_2,\ldots,k_K)$ are connected by an edge if for all $1\le i\le K$, $j_i$
and $k_i$ are connected by an edge in
$G_i$.

Define the distance between two vertices in $G$ 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,\ldots,1)$ and every vertex in the same component as it in $G$, modulo
$10^9+7$.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $K$, the number of graphs.

Each graph description starts with $N_i$ and $M_i$ on a single line, followed by
$M_i$ edges.

Consecutive graphs are separated by newlines for readability. It is guaranteed
that $\sum N_i\le 10^5$ and $\sum M_i\le 2\cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):
The sum of the distances between vertex $(1,1,\ldots,1)$ and every vertex that
is reachable from it, modulo $10^9+7$.

SAMPLE INPUT:
2

2 1
1 2

4 4
1 2
2 3
3 4
4 1
SAMPLE OUTPUT:
4

$G$ contains $2\cdot 4=8$ vertices, $4$ of which are not connected to vertex
$(1,1)$. There are $2$ vertices that are distance $1$ away from $(1,1)$ and $1$
that is distance $2$ away. So the answer is $2\cdot 1+1\cdot 2=4$.

SAMPLE INPUT:
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
SAMPLE OUTPUT:
706

$G$ contains $4\cdot 6\cdot 7=168$ vertices, all of which are connected to
vertex $(1,1,1)$. The number of vertices that are distance $i$ away from
$(1,1,1)$ for each $i\in [1,7]$ is given by the $i$-th element of the following
array:
$[4,23,28,36,40,24,12]$.

SCORING:
Test cases 3-4 satisfy $\prod N_i\le 300$.Test cases 5-10 satisfy $\sum N_i\le 300$.Test cases 11-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

见题面

见题面