H. Hamza and the Forgotten Tree Syndrome
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Later that night, Hamza, Ahmad, and Bahaa were sitting in the kitchen trying to come up with ideas to challenge each other. Hamza remembered that he had an undirected tree of $$$n$$$ nodes, and each node had an integer $$$c_i$$$ written on it.

To challenge Ahmad and Bahaa, Hamza gave them three functions:

$$$F(u, v) = $$$ The number of nodes on a simple path between nodes $$$u$$$ and $$$v$$$.

$$$G(u, v) = $$$ The greatest common divisor of each value $$$c_i$$$ where $$$i$$$ represents every node on the simple path between nodes $$$u$$$ and $$$v$$$.

$$$H(u, v) = F(u, v) \times G(u, v)$$$

And then he asked them to calculate the following summation: $$$$$$\left( \sum_{1 \leq u \lt v \leq N} H(u, v) \right) \mod 10^9 + 7$$$$$$ Can you help them find the answer?

Input

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of nodes in the given tree.

The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ $$$(1 \leq c_i \leq 10^5)$$$.

Then $$$n - 1$$$ lines follow, and each line contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u \lt v \leq n)$$$ indicating an edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that these edges form a tree.

Output

Print one integer, the summation as described in the statement.

Example
Input
5
8 1 13 26 1
1 2
1 4
4 3
4 5
Output
54