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 nodes and edges.
On every node of the tree, there exists one single fruit. For a fruit on node , it has a tiredness value of .
Every time Joe eats the fruits, he only travels the simple path from to (a simple path is a path that every node and edge is visited only once). When he travels from to , 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 that lies on the path from to is defined as , where denotes the rank of the fruit on node if you sort all the fruit on the simple path from to based on their tiredness values in increasing order. The whole tiredness of path (, ) 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

The first line contains one integer  ---the number of nodes on the tree.
The second line contains  integers ()---the tiredness value of every node on the tree.
The -th of the following  lines contains two integers  and  () denoting that there exists an edge connecting vertices  and . It is guaranteed that the given edges form a tree.

Print a single integer --- the tiredness sum of all paths on the tree module 

2
1 2
1 2

8

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

357

The path from  to  is considered the same as the path from  to .
Path with the form  is regarded as a valid simple path.