该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制： 1s

空间限制： 512MB

有一棵 $n$ 个点 $n-1$ 条边的树，每条边具有初始长度 $0$ 以及特征值 $w_i$ 。你在树上巡逻，对于第 $i$ 条边而言，你每巡逻过一次该边，该边的长度就会增加 $w_i$ 。接下来会给你 $m$ 个操作，每个操作有两种：

• 操作 $1$ : 给定三个数 $a_i,b_i,c_i$ ，你在 $a_i$ 到 $b_i$ 的道路上又跑了 $c_i$ 次。

• 操作 $2$ : 询问整棵树任意两点的距离和。

为了减少输出量，你无需对每次询问都输出答案，而是存储所有答案并求和。最终输出所有询问之和对 $10^9+7$ 取模之后的结果。

输入格式

第一行输入一个整数 $n$ ，代表树的节点个数。

接下来 $n-1$ 行每行输入三个数 $a_i,b_i,w_i(w_i \leq 10^4)$，代表一条树的边的信息。

接下来一行输入一个整数 $m$，代表总的操作次数。

接下来 $m$ 行每行首先输入一个整数 $op \ (1 \le op \le 2)$，代表此次操作的种类，若 $op=1$ ，则再输入三个数 $a_i,b_i,c_i(1 \le a_i,b_i \le n, 1 \le c_i \le 10 ^ 4)$ 。

输出格式

输出一行一个整数表示所有询问之和。

样例 1

输入

3
1 2 10
2 3 1
3
2
1 1 3 3
2

输出

66

样例解释

对于第一个查询答案是 $0$ ，第二个操作你把$1-2$与 $2-3$ 两条边均走了 $3$ 遍，此时 $1-2$ 边长为 $30$ ，$2-3$ 边长为 $3$ 。对于第二个询问，答案就是 $\text{dist}(1,2)+\text{dist}(1,3)+\text{dist}(2,3)=30+3+33=66$，因此两次查询的总和为 $0+66=66$

样例 2

见下发文件 patrol2.in/out.

数据范围