There are `N` (1 ≤ `N` ≤ 10^{5}) cities on land, and there are `N` - 1 wires connecting the cities. Therefore, each city can transmit electricity to all other cities by these wires.

Dark_Sun made a decision to build a nuclear power plant to supply electricity for all the cities. The nuclear power plant can be built in any city, but the cost for the electricity transmission is very strange. Let the weight of wire which connects city `u` and city `v` is `E`(u, v) (|`E`(u, v)| < 10^{9}). If the power plant is built in city `x`, the cost for electricity transmission from city `x` to city `y` is `D`(`x`, `y`) = (`E`(`x`, `s`_{1}) + `E`(`s`_{1}, `s`_{2}) + ... + `E`(`s`_{p}, `y`))^{k}, where {`x`, `s`_{1}, `s`_{2}, ..., `s`_{p}, `y`} is the path from `x` to `y`. Because of the bug of the computer, the total cost for building a nuclear power plant in city `x` is Σ(`D`(`x`, `i`)) mod 100000007 (0 ≤ `i` < `N`, `i` ≠ `x`), and the total cost is obviously not a negative number.

Dark_Sun asks you to write a program to calculate the minimum total cost.

提交代码