Persistent Link/cut Tree

Problem Description

Teacher Mai has $m+1$ trees, $T_0,T_1,\cdots,T_m$. $T_0$ consists one vertex numbered $0$. He generated the $T_i$ in this way. Get a copy of $T_{a_i}$ and $T_{b_i}$. Add an edge with length $l_i$ between vertex numbered $c_i$ in $T'_{a_i}$ and $d_i$ in $T'_{b_i}$. Relabel the vertices in the new tree. Let $k$ be the number of vertices in $T'_{a_i}$. He keeps labels of vertices in $T'_{a_i}$ the same, and adds $k$ to labels of vertices in $T'_{b_i}$. If there is a tree $T$ with $n$ vertices $v_0,v_1,v_2,\cdots,v_{n-1}$, $F(T)=\sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} d(v_i,v_j)$($d(v_i,v_j)$ means the distance between the $v_i$ and $v_j$). For every $i(1\leq i\leq m)$, he wants to know $F(T_i)$.

Input

There are multiple test cases(about $100$). For each test case, the first line contains one number $m(1\leq m\leq 60)$, the following are $m$ lines. The $i$-th lines contains five numbers $a_i,b_i,c_i,d_i,l_i(0\leq a_i,b_i<i,0\leq l_i\leq 10^9)$. It's guarenteed that there exists a vertex numbered $c_i$ in $T_{a_i}$ and there exists a vertex numbered $d_i$ in $T_{b_i}$.

Output

For each test case, print $F(T_i)$ modulo $10^9+7$ in the $i$-th line.

Sample Input

3
0 0 0 0 2
1 1 0 0 4
2 2 1 0 3

Sample Output

2
28
216

Author

xudyh

Source

2015 Multi-University Training Contest 9