1210_C. Kamil and Making a Stream
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, ..., 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}, ..., 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

$$$ ∑_{u 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 ≤ n ≤ 100 000) — the number of vertices in the tree.

The following line contains n integers x_1, x_2, ..., x_n (0 ≤ x_i ≤ 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 ≤ a, b ≤ n, a ≠ 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>
```python
from math import gcd
from collections import deque
from bisect import bisect_left
from sys import setrecursionlimit

MOD = 1000000007


def modInt(mod):
    class ModInt:

        def __init__(self, value):
            self.value = value % mod

        def __int__(self):
            return self.value

        def __eq__(self, other):
            return self.value == other.value

        def __hash__(self):
            return hash(self.value)

        def __add__(self, other):
            return ModInt(self.value + int(other))

        def __sub__(self, other):
            return ModInt(self.value - int(other))

        def __mul__(self, other):
            return ModInt(self.value * int(other))

        def __floordiv__(self, other):
            return ModInt(self.value // int(other))

        def __truediv__(self, other):
            return ModInt(self.value * pow(int(other), mod - 2, mod))

    return ModInt

ModInt = modInt(MOD)

def main():
    n = int(input())
    setrecursionlimit(n+100)
    xx = [0] + [int(x) for x in input().split()]
    edges = []
    neighbors = [[] for _ in range(n+1)]
    for _ in range(n-1):
        v1, v2 = [int(x) for x in input().split()]
        neighbors[v1].append(v2)
        neighbors[v2].append(v1)
    visited = [False] * (n+1)
    dq = deque()
    dq.append((1,[]))
    sum = ModInt(0)
    while dq:
        u,gcds = dq.popleft()
        gcdns = [[xx[u], 1]]
        sum = (sum + xx[u])
        for g, c in gcds:
            gcdn = gcd(xx[u], g)
            sum = (sum + gcdn*c)
            if gcdn == gcdns[-1][0]:
                gcdns[-1][1] += c
            else:
                gcdns.append([gcdn, c])
        visited[u] = True
        for v in neighbors[u]:
            if not visited[v]:
                dq.append((v, gcdns))
    print(int(sum))



if __name__ == "__main__":
    main()
```