题目描述

洗完衣服，就要晒在树上。但是这个世界并没有树,我们需要重新开始造树。我们一开始拥有T0 ，是一棵只有一个点的树，我们要用它造出更多的树。生成第i棵树我们需要五个参数ai,bi,ci,di,li(ai,bi<i)。我们生成第?棵树是将第ai棵树的bi号点和第ci棵树的di号点用一条长度为li的边连接起来形成的新的树（不会改变原来两棵树） 。下面我们需要对新树中的点重编号：对于原来在第ai棵树中的点，我们不会改变他们的编号；对于原来在第bi棵树中的点，我们会将他们的编号加上第ai棵树的点的个数作为新的编号。

定义
F(Ti)=∑(i=0,n-1)∑(j=i+1,n-1)d(vi,vj)

其中,n为树Ti的大小vi,vj是Ti中的点,d(vi,vj)代表这两个点的距离。
现在希望你求出∀1≤i≤m,F(Ti)是多少.

输入

第一行一个整数m，代表要造多少棵树。
接下来m行，每行5个数ai,bi,ci,di,li。

输出

m行每行一个整数代表F(Ti)对10^9+7取模之后的值。

输入样例

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

输出样例

2
28
216

限制

时间:1000ms
空间:256MB

数据范围

对于30%的数据，1<=m<=10;
对于60%的数据，每棵树的点数个数不超过10^5;
对于100%的数据，1<=m<=60。

p.s.

from 高天宇
manual input by autihero（微笑）