有一棵 $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$，代表一条树的边的信息。

接下来一行输入一个整数 $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)$

输出格式

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

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$

测试点说明