Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Building Forest

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAn oriented weighted forest is an acyclic weighted digraph in which from each vertex at most one edge goes.

The root of vertex *v* of an oriented weighted forest is a vertex from which no edge goes and which can be reached from vertex *v* moving along the edges of the weighted oriented forest. We denote the root of vertex *v* as *root*(*v*).

The depth of vertex *v* is the sum of weights of paths passing from the vertex *v* to its root. Let's denote the depth of the vertex *v* as *depth*(*v*).

Let's consider the process of constructing a weighted directed forest. Initially, the forest does not contain vertices. Vertices are added sequentially one by one. Overall, there are *n* performed operations of adding. The *i*-th (*i* > 0) adding operation is described by a set of numbers (*k*, *v*_{1}, *x*_{1}, *v*_{2}, *x*_{2}, ... , *v*_{k}, *x*_{k}) and means that we should add vertex number *i* and *k* edges to the graph: an edge from vertex *root*(*v*_{1}) to vertex *i* with weight *depth*(*v*_{1}) + *x*_{1}, an edge from vertex *root*(*v*_{2}) to vertex *i* with weight *depth*(*v*_{2}) + *x*_{2} and so on. If *k* = 0, then only vertex *i* is added to the graph, there are no added edges.

Your task is like this: given the operations of adding vertices, calculate the sum of the weights of all edges of the forest, resulting after the application of all defined operations, modulo 1000000007 (10^{9} + 7).

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of operations of adding a vertex.

Next *n* lines contain descriptions of the operations, the *i*-th line contains the description of the operation of adding the *i*-th vertex in the following format: the first number of a line is an integer *k* (0 ≤ *k* ≤ *i* - 1), then follow 2*k* space-separated integers: *v*_{1}, *x*_{1}, *v*_{2}, *x*_{2}, ... , *v*_{k}, *x*_{k} (1 ≤ *v*_{j} ≤ *i* - 1, |*x*_{j}| ≤ 10^{9}).

The operations are given in the order, in which they should be applied to the graph. It is guaranteed that sum *k* of all operations does not exceed 10^{5}, also that applying operations of adding vertexes does not result in loops and multiple edges.

Output

Print a single number — the sum of weights of all edges of the resulting graph modulo 1000000007 (10^{9} + 7).

Examples

Input

6

0

0

1 2 1

2 1 5 2 2

1 1 2

1 3 4

Output

30

Input

5

0

1 1 5

0

0

2 3 1 4 3

Output

9

Note

Conside the first sample:

- Vertex 1 is added.
*k*= 0, thus no edges are added. - Vertex 2 is added.
*k*= 0, thus no edges are added. - Vertex 3 is added.
*k*= 1.*v*_{1}= 2,*x*_{1}= 1. Edge from vertex*root*(2) = 2 to vertex 3 with weight*depth*(2) +*x*_{1}= 0 + 1 = 1 is added. - Vertex 4 is added.
*k*= 2.*v*_{1}= 1,*x*_{1}= 5. Edge from vertex*root*(1) = 1 to vertex 4 with weight*depth*(1) +*x*_{1}= 0 + 5 = 5 is added.*v*_{2}= 2,*x*_{2}= 2. Edge from vertex*root*(2) = 3 to vertex 4 with weight*depth*(2) +*x*_{1}= 1 + 2 = 3 is added. - Vertex 5 is added.
*k*= 1.*v*_{1}= 1,*x*_{1}= 2. Edge from vertex*root*(1) = 4 to vertex 5 with weight*depth*(1) +*x*_{1}= 5 + 2 = 7 is added. - Vertex 6 is added.
*k*= 1.*v*_{1}= 3,*x*_{1}= 4. Edge from vertex*root*(3) = 5 to vertex 6 with weight*depth*(3) +*x*_{1}= 10 + 4 = 14 is added.

The resulting graph is shown on the pictore below:

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2021 00:06:54 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|