Sum of Distances#11204
Bessie has a collection of (2 \le k \le 5 \cdot 10^4) connected, undirected graphs G_1, G_2, ..., G_k. G_i (1 \le i \le k) has exactly n_i (n_i \ge 2) vertices labeled ...n_i and m_i (m_i \ge n_i - 1) edges. Each G_i may contain cycles, but not multiple edges between the same pair of vertices.
Now Elsie creates a new undirected graph with n_1 \cdot n_2 \cdot \ldots \cdot n_k vertices, each labeled by a -tuple (j_1, j_2,..., j_k) where 1 \le j_i \le n_i. In , two vertices (j_1, j_2,...,j_k) and (k_1, k_2,..., 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 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 (, ,..., ) and every vertex in the same component as it in , modulo 10^9 + 7.
The first line contains , 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.
Print the sum of the distances between vertex (, ,..., ) and every vertex that is reachable from it, modulo 10^9 + 7.
Example 1
Example 2
**Example 1**
contains 2 \cdot 4 = 8 vertices, of which are not connected to vertex (, ). There are vertices that are distance away from (, ) and that is distance away. So the answer is 2 \cdot 1 + 1 \cdot 2 = 4.
**Example 2**
contains 4 \cdot 6 \cdot 7 = 168 vertices, all of which are connected to vertex (, , ). The number of vertices that are distance away from (, , ) for each i \in [1, 7] is given by the -th element of the following array: [, , , , , , ].