Bessie has a collection of connected, undirected graphs G1, G2, ..., Gk. Gi (1 ≤ i ≤ k) 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 i (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.

Input

The first line contains k (2 ≤ k ≤ 5 * 104), 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 ∑ ni ≤ 105 and ∑ mi ≤ 2 * 105.

Output

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

Example 1

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.

Example 2

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