你正在为 KAIST RUN ICPC 2025 竞赛做准备，却完全忘记了提交微积分作业。现在教授宣布了“审判日”（Judgement Day）。

他释放了传奇的 Hubo 机器人，它的程序中只有一个任务：在校园的任何地方找到你，并温柔地督促你完成作业。

KAIST 校园可以建模为由 $n$ 栋建筑和 $n - 1$ 条道路组成的树。每条道路 $(u, v)$ 都有一个道路拥堵度 $w(u, v)$。

当 Hubo 位于地点 $x$ 时，它会随机选择下一步的移动。对于 $x$ 的每个邻居 $y$，Hubo 从 $x$ 移动到 $y$ 的概率为：

$$\Pr[x \to y] = \frac{\frac{1}{w(x,y)}}{\sum_{z \sim x} \frac{1}{w(x,z)}}$$

其中 $w(x, y)$ 是道路 $(x, y)$ 的拥堵度，$z \sim x$ 表示 $x$ 的所有邻居。

对你来说不幸的是，教授可以随着时间的推移改变校园道路，从而改变它们的负载。

你必须处理 $q$ 个事件：

• 1 id new_w — 索引为 id 的道路的拥堵度变为 new_w；
• 2 u v — 你躲在地点 $v$，而 Hubo 被部署在地点 $u$。输出 Hubo 到达你身边所需的期望步数。如果 $u = v$，则答案为 0。

由于期望值可能是有理数，请将其对 $10^9 + 7$ 取模后输出。形式上，如果最简分数形式的期望值为 $s/t$，则输出 $s \times t^{-1} \pmod{10^9 + 7}$，其中 $t^{-1}$ 是 $t$ 模 $10^9 + 7$ 的乘法逆元。

输入格式

第一行包含两个整数 $n$ 和 $q$。

接下来的 $n - 1$ 行中，每行包含三个整数 $a, b, w$，描述一条连接地点 $a$ 和 $b$ 且拥堵度为 $w$ 的道路（$1 \le a, b \le n$）。道路按它们出现的顺序依次索引为 $1, \dots, n-1$。

接下来的 $q$ 行，每行包含一个上述格式的事件。

输出格式

对于每个类型为 2 的询问，输出一个整数，表示期望步数模 $10^9 + 7$ 的结果。

数据范围

• $3 \le n, q \le 2 \cdot 10^5$
• 对于每条道路的拥堵度 $w$，$1 \le w \le 10^9$

样例

输入样例 1

4 7
1 2 1
2 3 1
3 4 1
2 1 4
2 4 1
1 2 2
2 1 4
1 1 5
2 4 1
2 3 3

输出样例 1

9
9
10
22
0