J. Rasoulo and the Heavy Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Hosen found a massive, incredibly heavy tree with $$$n$$$ nodes. The tree was special: each node had a value $$$a_i$$$ written on it, forming a permutation of integers from $$$0$$$ to $$$n-1$$$.

Without warning, Hosen threw the giant tree right into Rasoulo's arms!

"Hold the tree! Don't let it fall!" Hosen shouted as he started running away. "I am going to get us some shawarma. I will calculate its paths when I get back!"

Now, Rasoulo is stuck holding the tree. His arms are shaking, his back hurts, and he is sweating. The tree is so heavy! He desperately wants to put it down. To finish the task before his arms completely give out, Rasoulo decides to calculate the answer himself.

For any simple path between node $$$u$$$ and node $$$v$$$ ($$$u \lt v$$$), we define:

  • The length of the path as the number of edges between $$$u$$$ and $$$v$$$.
  • The MEX of the path as the smallest non-negative integer that does not appear on any node along the path.

Rasoulo wants to calculate the total sum of $$$F(u, v)$$$ for all valid pairs of nodes $$$(u, v)$$$ such that $$$u \lt v$$$, where: $$$$$$F(u, v) = \text{length}(u, v) \times \text{MEX}(u, v)$$$$$$

Since the answer can be very large, print it modulo $$$10^9 + 7$$$. Can you help Rasoulo calculate the answer so he can finally drop the tree?

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of nodes in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \lt n$$$) — the values written on the nodes. It is guaranteed that all $$$a_i$$$ are distinct (the array $$$a$$$ is a permutation).

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), denoting an edge between node $$$u$$$ and node $$$v$$$. It is guaranteed that the given edges form a valid tree.

Output

Print a single integer — the sum of $$$F(u, v)$$$ for all pairs of nodes $$$u \lt v$$$, modulo $$$10^9 + 7$$$.

Example
Input
4
0 2 1 3
1 2
2 3
2 4
Output
9
Note

In the given sample, the tree has $$$4$$$ nodes. The values on the nodes are: $$$a_1 = 0$$$, $$$a_2 = 2$$$, $$$a_3 = 1$$$, and $$$a_4 = 3$$$. Let's analyze all valid pairs $$$(u, v)$$$ where $$$u \lt v$$$:

  • Pair (1, 2): The path is $$$1 \to 2$$$. The values on the path are $$$\{0, 2\}$$$. The length is $$$1$$$. The MEX is $$$1$$$ (since $$$0$$$ is present, but $$$1$$$ is missing). $$$F(1, 2) = 1 \times 1 = 1$$$.
  • Pair (1, 3): The path is $$$1 \to 2 \to 3$$$. The values on the path are $$$\{0, 2, 1\}$$$. The length is $$$2$$$. The MEX is $$$3$$$ (since $$$0, 1, 2$$$ are all present). $$$F(1, 3) = 2 \times 3 = 6$$$.
  • Pair (1, 4): The path is $$$1 \to 2 \to 4$$$. The values on the path are $$$\{0, 2, 3\}$$$. The length is $$$2$$$. The MEX is $$$1$$$. $$$F(1, 4) = 2 \times 1 = 2$$$.
  • Pair (2, 3): The path is $$$2 \to 3$$$. The values on the path are $$$\{2, 1\}$$$. The length is $$$1$$$. The MEX is $$$0$$$. $$$F(2, 3) = 1 \times 0 = 0$$$.
  • Pair (2, 4): The path is $$$2 \to 4$$$. The values on the path are $$$\{2, 3\}$$$. The length is $$$1$$$. The MEX is $$$0$$$. $$$F(2, 4) = 1 \times 0 = 0$$$.
  • Pair (3, 4): The path is $$$3 \to 2 \to 4$$$. The values on the path are $$$\{1, 2, 3\}$$$. The length is $$$2$$$. The MEX is $$$0$$$ (since $$$0$$$ is missing). $$$F(3, 4) = 2 \times 0 = 0$$$.

The total sum is $$$1 + 6 + 2 + 0 + 0 + 0 = 9$$$.