有向加权森林是一种非循环加权有向图,其中每个顶点最多有一条边。
定向加权森林的顶点v的根是没有边从其出发并且可以从沿加权定向森林的边缘移动的顶点v到达的顶点。我们将顶点 v 的根表示为 root(v)。
顶点 v 的深度是从顶点 v 到其根的路径权重之和。我们将顶点 v 的深度表示为深度(v)。
让我们考虑一下构建加权有向森林的过程。最初,森林不包含顶点。顶点按顺序一一添加。总共执行了n次加法操作。第 i (i > 0) 个加法操作由一组数字 (k, v1, x1, v2, x2, ... , vk, xk) 描述,意味着我们应该将顶点编号 i 和 k 条边添加到图中:从顶点根 (v1) 到顶点 i 的边,权重深度 (v1) + x1,从顶点根 (v2) 到顶点 i 的边,权重深度 (v2) + x2 等等。如果 k = 0,则仅将顶点 i 添加到图中,不添加边。
你的任务是这样的:给定添加顶点的操作,计算森林所有边的权重总和,这是应用所有定义的操作后的结果,模 1000000007 (109 + 7)。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 添加顶点的操作次数。
接下来 n 行包含操作描述,第 i 行包含添加第 i 个顶点的操作描述,格式如下:一行的第一个数字是整数 k (0 ≤ k ≤ i - 1),然后是 2k 个空格分隔的整数: v1, x1, v2, x2, ... , vk, xk (1 ≤ vj ≤ i - 1, |xj| ≤ 109)。
操作按顺序给出,应按顺序将它们应用于图表。保证所有操作的和k不超过105,并且应用添加顶点的操作不会导致循环和多边。
输出
打印一个数字 — 所得图的所有边的权重之和以 1000000007 (109 + 7) 为模。
示例
输入 #1
6 0 0 1 2 1 2 1 5 2 2 1 1 2 1 3 4
输出 #1
30
输入 #2
5 0 1 1 5 0 0 2 3 1 4 3
输出 #2
9
注意
考虑第一个示例:
1. 添加顶点 1。 k = 0,因此不添加边。
2. 添加顶点 2。 k = 0,因此不添加边。
3. 添加顶点 3。 k = 1。v1 = 2,x1 = 1。添加从顶点根(2) = 2到顶点3、权重深度(2) + x1 = 0 + 1 = 1的边。
4. 添加顶点 4。 k = 2。v1 = 1,x1 = 5。添加从顶点根(1) = 1到顶点4、权重深度(1) + x1 = 0 + 5 = 5的边。 v2 = 2,x2 = 2。添加从顶点 root(2) = 3 到顶点 4 的边,权重深度为(2) + x1 = 1 + 2 = 3。
5. 添加顶点 5。 k = 1。v1 = 1,x1 = 2。添加从顶点根(1) = 4到顶点5、权重深度(1) + x1 = 5 + 2 = 7的边。
6. 添加顶点 6。 k = 1。v1 = 3,x1 = 4。添加从顶点根(3) = 5到顶点6、权重深度(3) + x1 = 10 + 4 = 14的边。
结果图表如下图所示: