Bessie has a collection of connected, undirected graphs G1**,G2**,…,GKG1,G2,…,GK (2≤K≤5⋅1042≤K≤5⋅104). For each 1≤i≤K1≤i≤K, GiGi has exactly NiNi (Ni≥2Ni≥2) vertices labeled 1…Ni1…Ni and MiMi (Mi≥Ni−1Mi≥Ni−1) edges. Each GiGi may contain self-loops, but not multiple edges between the same pair of vertices.Now Elsie creates a new undirected graph GG with N1⋅N2⋯NKN1⋅N2⋯NK vertices, each labeled by a KK-tuple (j1,j2**,…,jK**)(j1,j2,…,jK) where 1≤ji≤Ni1≤ji≤Ni. In GG, two vertices (j1,j2**,…,jK**)(j1,j2,…,jK) and (k1,k2**,…,kK**)(k1,k2,…,kK) are connected by an edge if for all 1≤i≤K1≤i≤K, jiji and kiki are connected by an edge in GiGi.

Define the distance between two vertices in GG 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)(1,1,…,1) and every vertex in the same component as it in GG, modulo 109**+**7109+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains KK, the number of graphs.Each graph description starts with NiNi and MiMi on a single line, followed by MiMi edges.

Consecutive graphs are separated by newlines for readability. It is guaranteed that ∑Ni≤105∑Ni≤105 and ∑Mi≤2⋅105∑Mi≤2⋅105.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

SAMPLE OUTPUT:

4

GG contains 2⋅4=82⋅4=8 vertices, 44 of which are not connected to vertex (1,1)(1,1). There are 22 vertices that are distance 11 away from (1,1)(1,1) and 11 that is distance 22 away. So the answer is 2⋅1+1⋅2=42⋅1+1⋅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

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

SCORING:

• Test cases 3-4 satisfy ∏Ni≤300∏Ni≤300.
• Test cases 5-10 satisfy ∑Ni≤300∑Ni≤300.
• Test cases 11-20 satisfy no additional constraints.