20964번 - Sum of Distances 다국어

문제

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

입력

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

출력

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

제한

힌트