Problem Description
Teacher Mai has m+1 trees, T0,T1,⋯,Tm. T0 consists one vertex numbered 0.
He generated the Ti in this way. Get a copy of Tai and Tbi. Add an edge with length li between vertex numbered ci in T′ai and di in T′bi. Relabel the vertices in the new tree. Let k be the number of vertices in T′ai. He keeps labels of vertices in T′ai the same, and adds k to labels of vertices in T′bi.
If there is a tree T with n vertices v0,v1,v2,⋯,vn−1, F(T)=∑n−1i=0∑n−1j=i+1d(vi,vj)(d(vi,vj) means the distance between the vi and vj).
For every i(1≤i≤m), he wants to know F(Ti).
Input
There are multiple test cases(about 100).
For each test case, the first line contains one number m(1≤m≤60), the following are m lines. The i-th lines contains five numbers ai,bi,ci,di,li(0≤ai,bi<i,0≤li≤109). It's guarenteed that there exists a vertex numbered ci in Tai and there exists a vertex numbered di in Tbi.
Output
For each test case, print F(Ti) modulo 109+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