철도 2

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$번 도시에 도착할 때까지 내릴 수 없다. 이 열차의 소요 시간은 철도망에서 $u$번 도시와 $v$번 도시를 잇는 유일한 단순 경로 위 철도들의 길이를 합한 값과 같다.

서로 다른 두 도시 $x$, $y$에 대하여 즐거움 $\text{joy}(x, y)$는 다음 조건을 만족하는 최대의 양의 정수 $D$로 정의한다. $x$번 도시에서 출발해 소요 시간이 $D$ 이상인 직통 열차만 타고 유한 번 이동하여 $y$번 도시에 도착할 수 있다.

$0 \le x, y \le N - 1$, $x \neq y$인 모든 $N(N - 1)$개의 순서쌍 $(x, y)$에 대한 $\text{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$).