[USACO Jan 2021 P] Sum of Distances
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Bessie has a collection of connected, undirected graphs . For each 1≤i≤K, Gi has exactly Ni (Ni≥2) vertices labeled 1…Ni and Mi (Mi≥Ni−1) edges. Each Gi may contain self-loops, but not multiple edges between the same pair of vertices.
Now Elsie creates a new undirected graph G with N1⋅N2⋯NK vertices, each labeled by a K-tuple (j1,j2,…,jK) where 1≤ji≤Ni. In G, two vertices (j1,j2,…,jK) and (k1,k2,…,kK) are connected by an edge if for all 1≤i≤K, ji and ki are connected by an edge in Gi.

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,…,1) and every vertex in the same component as it in G, modulo 109+7.

输入描述:

The first line contains K, the number of graphs.
Each graph description starts with Ni and Mi on a single line, followed by Mi edges.

Consecutive graphs are separated by newlines for readability. It is guaranteed that  and .

输出描述:

The sum of the distances between vertex (1,1,…,1) and every vertex that is reachable from it, modulo 109+7.
示例1

输入

复制 
2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

输出

复制 
4

说明

G  contains 2⋅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⋅1+1⋅2=4.
示例2

输入

复制 
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

说明

G contains 4⋅6⋅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∈[1,7] is given by the i-th element of the following array: [4,23,28,36,40,24,12].