Kamil likes streaming the competitive programming videos. His MeTube channel has recently reached $100$ million subscribers. In order to celebrate this, he posted a video with an interesting problem he couldn't solve yet. Can you help him?

You're given a tree — a connected undirected graph consisting of $n$ vertices connected by $n - 1$ edges. The tree is rooted at vertex $1$. A vertex $u$ is called an ancestor of $v$ if it lies on the shortest path between the root and $v$. In particular, a vertex is an ancestor of itself.

Each vertex $v$ is assigned its beauty $x_v$ — a non-negative integer not larger than $10^{12}$. This allows us to define the beauty of a path. Let $u$ be an ancestor of $v$. Then we define the beauty $f(u, v)$ as the greatest common divisor of the beauties of all vertices on the shortest path between $u$ and $v$. Formally, if $u=t_1, t_2, t_3, \dots, t_k=v$ are the vertices on the shortest path between $u$ and $v$, then $f(u, v) = \gcd(x_{t_1}, x_{t_2}, \dots, x_{t_k})$. Here, $\gcd$ denotes the greatest common divisor of a set of numbers. In particular, $f(u, u) = \gcd(x_u) = x_u$.

Your task is to find the sum

$$ \sum_{u\text{ is an ancestor of }v} f(u, v). $$

As the result might be too large, please output it modulo $10^9 + 7$.

Note that for each $y$, $\gcd(0, y) = \gcd(y, 0) = y$. In particular, $\gcd(0, 0) = 0$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 100\,000$) — the number of vertices in the tree.

The following line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^{12}$). The value $x_v$ denotes the beauty of vertex $v$.

The following $n - 1$ lines describe the edges of the tree. Each of them contains two integers $a, b$ ($1 \le a, b \le n$, $a \neq b$) — the vertices connected by a single edge.


-----Output-----

Output the sum of the beauties on all paths $(u, v)$ such that $u$ is ancestor of $v$. This sum should be printed modulo $10^9 + 7$.


-----Examples-----
Input
5
4 5 6 0 8
1 2
1 3
1 4
4 5

Output
42

Input
7
0 2 3 0 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

Output
30



-----Note-----

The following figure shows all $10$ possible paths for which one endpoint is an ancestor of another endpoint. The sum of beauties of all these paths is equal to $42$: [Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())
beauty = list(map(int, input().strip().split()))
tree = [[] for i in range(n)]
mod = 1000000007
used = [False for i in range(n)]
def gcd(a,b):
    mn = min(a,b)
    mx = max(a,b)
    if mn == 0:
        return mx
    md = mx%mn
    if md == 0:
        return mn
    else:
        return gcd(mn, md)
for i in range(n-1):
    a,b = map(int, input().strip().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
segment_vals = [{} for i in range(n)]
ans = beauty[0]
segment_vals[0][beauty[0]] = 1
cur_nodes = [0]
used[0] = True
while 1:
    new_nodes = []
    for node in cur_nodes:
        for potential_new in tree[node]:
            if used[potential_new] == False:
                used[potential_new] = True
                new_nodes.append(potential_new)
                new_beauty = beauty[potential_new]
                segment_vals[potential_new][new_beauty] = 1
                for g in segment_vals[node].keys():
                    segment_gcd = gcd(new_beauty,g)
                    segment_vals[potential_new][segment_gcd] = segment_vals[potential_new].get(segment_gcd,0) + segment_vals[node][g]
                for k in segment_vals[potential_new].keys():
                    ans += k*segment_vals[potential_new][k]
                    ans = ans % mod
    if len(new_nodes) == 0:
        break
    else:
        cur_nodes = new_nodes
print(ans)