在遥远的未来，人类已经进驻了无数外星行星。行星 X 就是其中之一，太空探索公司 MR 在行星 X 上建立了多个基地，以进行探索和资源开采活动。

行星 X 上有 $N$ 个基地以及连接这些基地的 $N - 1$ 条双向通道，任意两个不同的基地之间都可以仅通过通道相互到达。也就是说，行星 X 的基地和通道构成了一棵树。

每个基地都被赋予了一个 $0$ 到 $N - 1$ 之间互不相同的编号。对于所有 $0 \le i \le N - 2$，第 $i$ 条通道连接 $U[i]$ 号基地和 $V[i]$ 号基地，通道的长度为 $W[i]$ km。

随着行星 X 的开发进入稳定期，由于维护所有基地和通道的成本很高，MR 决定只保留部分基地，并停用其余基地。

假设对于某个 $(s, e)$ ($0 \le s \le e \le N - 1$)，决定只保留编号为 $s, s+1, \dots, e$ 的基地。此时，维护成本定义如下：

• 选择 $0$ 条或多条通道以满足以下条件。此时，选择的通道长度之和应最小。（若选择了 $0$ 条通道，长度之和为 $0$ km。）
  • 对于任意 $u, v$ ($s \le u < v \le e$)，编号为 $u$ 的基地和编号为 $v$ 的基地可以通过所选通道相互到达。中间经过已停用的基地是没有关系的。
• 当所选通道的长度之和为 $C$ km 时，维护成本为 $C$。

由于尚未决定保留哪些基地，MR 希望计算出对于所有可能的 $(i, j)$ ($0 \le i \le j \le N - 1$) 对，仅保留编号为 $i, i+1, \dots, j$ 的基地时的维护成本之和。你需要为 MR 计算该值。由于结果可能非常大，请输出其对 $1\,000\,000\,007$ 取模后的余数。

实现细节

你需要实现以下函数：

int maintenance_costs_sum(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]$ km 的通道。
• 该函数应返回对于所有可能的 $(i, j)$ ($0 \le i \le j \le N - 1$) 对，仅保留编号为 $i, i+1, \dots, j$ 的基地时的维护成本之和，对 $1\,000\,000\,007$ 取模后的结果。

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

数据范围

• $2 \le N \le 250\,000$
• 对于所有 $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 10^9$ ($0 \le i \le N - 2$)

子任务

1. (5分) $N \le 300$
2. (6分) $N \le 4\,000$
3. (10分) 基地编号为以 $0$ 号基地为根的树的先序遍历（Preorder）顺序之一。
4. (26分) 每个基地连接的通道最多为 $2$ 条。
5. (53分) 无额外限制。

样例

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

评测程序调用以下函数：

maintenance_costs_sum([0, 2, 2, 0], [2, 1, 4, 3], [2, 3, 6, 5])

下图展示了行星 X 的基地及通道布局：

对于所有可能的 $(i, j)$ 对，计算出的维护成本如下表所示：

函数应返回 $98$。

Sample grader

Sample grader 接收以下格式的输入：

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

Sample grader 输出以下内容：

• 第 1 行：maintenance_costs_sum 的返回值

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