409709: GYM103688 K Monkey Joe

Monkey Joe likes to eat fruit. As monkey Joe is fond of climbing here and there, rather than eating fruits that are already in the grocery shops, he choose to climb the tree and eat the fruit on the tree.

A tree is a connected graph containing $$$n$$$ nodes and $$$n-1$$$ edges. On every node of the tree, there exists one single fruit. For a fruit on node $$$u$$$, it has a tiredness value of $$$val_{u}$$$.

Every time Joe eats the fruits, he only travels the simple path from $$$u$$$ to $$$v$$$ (a simple path is a path that every node and edge is visited only once). When he travels from $$$u$$$ to $$$v$$$, he will eat every fruit on the simple path. However, Joe gets very tired of eating all the fruits.

Formally, his tiredness of eating fruit $$$i$$$ that lies on the path from $$$u$$$ to $$$v$$$ is defined as $$$rank_{i} \times val_{i}$$$, where $$$rank_{i}$$$ denotes the rank of the fruit on node $$$i$$$ if you sort all the fruit on the simple path from $$$u$$$ to $$$v$$$ based on their tiredness values in increasing order. The whole tiredness of path ($$$u$$$, $$$v$$$) is the sum of the tiredness of eating every fruit on the path. It is guaranteed that the tiredness value of each fruit are distinct.

Joe is uncertain which path he would choose to climb, so he would like you to calculate the tiredness sum of all distinct paths of the tree. Since the answer may be very large, you only have to output the answer module $$$10^9+7$$$

The first line contains one integer $$$n$$$ $$$(1 \leqslant n \leqslant 5 \times 10^5)$$$—the number of nodes on the tree.

The second line contains $$$n$$$ integers $$$val_{1},val_{2},...val_{n}$$$($$$1 \leqslant val_{i} \leqslant 10^9$$$)—the tiredness value of every node on the tree.

The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$u_{i}$$$ and $$$v_{i}$$$ ($$$1 \leqslant u_{i},v_{i} \leqslant n$$$) denoting that there exists an edge connecting vertices $$$u_{i}$$$ and $$$v_{i}$$$. It is guaranteed that the given edges form a tree.

Print a single integer — the tiredness sum of all paths on the tree module $$$10^9+7$$$

2
1 2
1 2

8

5
1 2 9 8 4
1 3
1 2
2 5
5 4

357

The path from $$$u$$$ to $$$v$$$ is considered the same as the path from $$$v$$$ to $$$u$$$.

Path with the form $$$(u,u)$$$ is regarded as a valid simple path.