Alice is playing with a tree consisting of N nodes, each with its own unique value. For any two distinct nodes x and y, she wants to compute a special score h(x, y) for each pair. Here’s how she defines it:

Maximum Value on Path f(x, y): This is the highest value among all nodes on the path connecting x and y.

Minimum Value on Path g(x, y): This is the lowest value among all nodes on the same path.

Special Score h(x, y): This is simply the product of f(x, y) and g(x, y), or h(x,y)=f(x,y)*g(x,y)

Alice wants to calculate the total sum of h(x, y) for every unique pair of nodes (x, y) where x ≠ y. Since the result might be huge, give the final answer modulo 1e9 + 7

Input Format The first line contains an integer N denoting the number of nodes in the tree.

The second line contains N space-separated integers A1, A2, ..., AN denoting the values associated with each node.

The next N — 1 lines each contain two integers ui, vi, denoting an edge between nodes ui and vi.

constraints-> 1≤N≤2×10^5

ANY IDEA FOR THIS PROBLEM?