枇杷树（loquat）

【题目背景】

杨吞天家有个很大的后院，但是光秃秃的，看起来很是荒凉。杨吞天决定种一个枇杷树

种子。许多年后，杨吞天的后院已经长满了“亭亭如盖”的枇杷树。

【题目描述】

杨吞天观察了枇杷树林的生长规律，他惊奇地发现，每一棵长出的枇杷树和之前长出的

枇杷树有着令人惊奇的相似性！

具体来说，每一年都会新长出一颗枇杷树，第i年长出的枇杷树记为Ti。第 0 年长出来

的枇杷树T 0 由于只是一个种子，因此它是一棵只有一个结点的树，该结点编号为 0 。

对于每个Ti（i > 0 ），都可以用 5 个参数来描述它，xi, yi, ui, vi, wi（xi, yi< i）。表示将

Txi的ui号结点和Tyi的vi号结点用一条长度为wi的边连结起来得到了Ti（注意，xi可以

等于yi，并且生成新树的时候用了两棵树）。

杨吞天将每年的树上的结点进行了重新编号，具体来说：对于第i年长出来的枇杷树，在

第xi棵树中点的编号不会变，在yi棵树中的点的编号加上第xi棵树的大小作为新的编号。

杨吞天很喜欢吃枇杷，每棵树上的每个结点都有一个枇杷。他想知道每棵树上任意两个

枇杷间的距离之和。由于答案可能很大，你只需要输出答案对 109 + 7取模的结果就可以了。

【输入格式】

从文件 loquat.in 中读入数据。

输入共若干行。

第一行一个正整数m，表示有m年。

接下来m行，每行 5 个非负整数xi, yi, ui, vi, wi描述Ti。

【输出格式】

输出到文件 loquat.out 中。

输出一共m行，每行一个非负整数，第i行的输出表示Ti对应的答案对 109 + 7取模的结果。

【样例 1 输入】

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

【样例 1 输出】

1 3
2 14
3 76
4 26

【样例 2 】

见选手目录下的 loquat/loquat2.in 与 loquat/loquat2.ans 。

【测试点约束】 对于所有测试点，满足 1 ≤m≤ 300 ， 0 ≤xi, yi< i。