Xây dựng rừng

Một rừng có hướng có trọng số là một đồ thị có hướng không chu trình, có trọng số, trong đó từ mỗi đỉnh có nhiều nhất một cung đi ra.

Gốc của đỉnh $v$, ký hiệu $root(v)$, là đỉnh không có cung đi ra và có thể đến được từ $v$ bằng cách di chuyển dọc theo các cung. Độ sâu của đỉnh $v$, ký hiệu $depth(v)$, là tổng trọng số các cung trên đường đi từ $v$ đến gốc của nó.

Ta xây dựng rừng bằng $N$ thao tác thêm đỉnh, thực hiện lần lượt. Thao tác thứ $i$ được mô tả bởi bộ số $(k,v_1,x_1,v_2,x_2,\dots ,v_k,x_k)$ và có nghĩa: thêm đỉnh số $i$ cùng $k$ cung vào đồ thị, trong đó cung thứ $j$ đi từ đỉnh $root(v_j)$ đến đỉnh $i$ với trọng số $depth(v_j)+x_j$ (các giá trị $root$ và $depth$ được tính tại thời điểm thêm cung đó). Nếu $k=0$ thì chỉ thêm đỉnh $i$, không thêm cung nào.

Hãy tính tổng trọng số tất cả các cung của rừng thu được sau khi thực hiện toàn bộ $N$ thao tác, theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$: số thao tác thêm đỉnh.
• $N$ dòng tiếp theo, dòng thứ $i$ mô tả thao tác thêm đỉnh $i$: bắt đầu là số nguyên $k$ ($0\le k\le i-1$), sau đó là $2k$ số nguyên $v_1,x_1,v_2,x_2,\dots ,v_k,x_k$.

Các thao tác được cho theo đúng thứ tự áp dụng. Dữ liệu đảm bảo việc thêm đỉnh không tạo ra khuyên (cung nối một đỉnh với chính nó) hay cung bội.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng trọng số tất cả các cung của đồ thị cuối cùng, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le v_j\le i-1$, $|x_j|\le {10}^9$
• Tổng các giá trị $k$ của tất cả thao tác không vượt quá ${10}^5$

Ví dụ