IOI 国由 $N$ 个城市和连接这些城市的 $N-1$ 条双向铁路组成，任意两个不同的城市之间都可以仅通过铁路往来。也就是说，IOI 国的铁路网构成了一棵树。城市编号为 $0$ 到 $N-1$，铁路编号为 $0$ 到 $N-2$。对于所有 $0 \le i \le N-2$，第 $i$ 条铁路连接城市 $U[i]$ 和城市 $V[i]$，其长度为 $W[i]$。

在 IOI 国，无论从哪个城市出发，都可以乘坐直达列车直接前往另一个城市。即对于所有 $0 \le u, v \le N-1, u \neq v$ 的 $N(N-1)$ 个有序对 $(u, v)$，都有一班从城市 $u$ 出发到达城市 $v$ 的直达列车。一旦在城市 $u$ 乘坐该直达列车，在到达城市 $v$ 之前不能下车，该直达列车的耗时等于 IOI 国铁路网中从城市 $u$ 到城市 $v$ 的唯一简单路径上所有铁路长度之和。

作为一名铁路爱好者，你喜欢在长途列车上享受悠闲时光，因此乘坐耗时越长的直达列车，你感到的乐趣就越大。

具体来说，对于两个不同的城市 $x, y$，乐趣 $joy(x, y)$ 定义为满足以下条件的最大正整数 $D$：

• 从城市 $x$ 出发，通过有限次乘坐耗时至少为 $D$ 的直达列车，可以到达城市 $y$。

请编写一个程序，计算所有满足 $0 \le x, y \le N-1, x \neq y$ 的 $N(N-1)$ 个有序对 $(x, y)$ 的 $joy(x, y)$ 之和，并对 $1\,000\,000\,007$ ($= 10^9 + 7$) 取模。

实现细节

你需要实现以下函数：

int travel(vector<int> U, vector<int> V, vector<int> W)

• 该函数仅会被调用一次。
• $U, V, W$：大小为 $N-1$ 的整数数组。对于所有 $i$ ($0 \le i \le N-2$)，存在一条连接城市 $U[i]$ 和 $V[i]$、长度为 $W[i]$ 的铁路。
• 该函数应返回所有满足 $0 \le x, y \le N-1, x \neq y$ 的 $N(N-1)$ 个有序对 $(x, y)$ 的 $joy(x, y)$ 之和对 $1\,000\,000\,007$ ($= 10^9 + 7$) 取模后的结果。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 500\,000$
• IOI 国的铁路网构成树结构。
• 对于所有 $i$，有 $0 \le U[i], V[i] \le N-1$；$U[i] \neq V[i]$ ($0 \le i \le N-2$)
• 对于所有 $i$，有 $1 \le W[i] \le 1\,000\,000\,000$ ($0 \le i \le N-2$)

子任务

1. (3 分) $N \le 50$
2. (6 分) $N \le 500$
3. (19 分) $N \le 2\,000$
4. (5 分) $N \le 8\,000$，且对于所有 $i$，$U[i] = 0$ ($0 \le i \le N-2$)
5. (7 分) $N \le 8\,000$，且对于所有 $i$，$U[i] = i, V[i] = i+1$ ($0 \le i \le N-2$)
6. (15 分) $N \le 8\,000$
7. (4 分) 对于所有 $i$，$U[i] = 0$ ($0 \le i \le N-2$)
8. (11 分) 对于所有 $i$，$U[i] = i, V[i] = i+1$ ($0 \le i \le N-2$)
9. (30 分) 无额外限制。

样例

样例 1

考虑 $N = 5, U = [0, 1, 0, 0], V = [1, 2, 3, 4], W = [1, 2, 3, 2]$ 的情况。

• $joy(0, 1) = 3$。可以从城市 $0$ 乘车到城市 $2$，再从城市 $2$ 乘车到城市 $4$，最后从城市 $4$ 乘车到城市 $1$。三班直达列车的耗时分别为 $3, 5, 4$。
• $joy(1, 2) = 4$。可以从城市 $1$ 乘车到城市 $3$，再从城市 $3$ 乘车到城市 $2$。两班直达列车的耗时分别为 $4, 6$。
• $joy(2, 3) = 6$。可以直接从城市 $2$ 乘车到城市 $3$。该直达列车的耗时为 $6$。

函数应返回 $80$。

样例 2

考虑 $N = 5, U = [0, 0, 0, 0], V = [1, 2, 3, 4], W = [3, 2, 2, 1]$ 的情况。

函数应返回 $78$。

样例 3

考虑 $N = 6, U = [0, 1, 2, 3, 4], V = [1, 2, 3, 4, 5], W = [3, 1, 4, 1, 5]$ 的情况。

函数应返回 $284$。

说明

Sample grader 的输入格式如下：

• 第 1 行：$N$
• 第 $2+i$ 行 ($0 \le i \le N-2$)：$U[i] \ V[i] \ W[i]$

Sample grader 的输出格式如下：

• 第 1 行：travel 函数的返回值

请注意，Sample grader 可能与实际评测时使用的 grader 不同。