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>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Map;
import java.util.Map.Entry;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EKamilAndMakingAStream solver = new EKamilAndMakingAStream();
        solver.solve(1, in, out);
        out.close();
    }

    static class EKamilAndMakingAStream {
        long mod = (long) 1e9 + 7;

        public void solve(int testNumber, FastReader s, PrintWriter w) {
            int n = s.nextInt();
            long[] x = new long[n];
            for (int i = 0; i < n; i++) x[i] = s.nextLong();
            ArrayList<Integer>[] a = new ArrayList[n];
            for (int i = 0; i < n; i++) a[i] = new ArrayList<>();
            for (int i = 1; i < n; i++) {
                int u = s.nextInt() - 1, v = s.nextInt() - 1;
                a[u].add(v);
                a[v].add(u);
            }
            w.println(dfs(0, -1, x, a, new HashMap<>()));
        }

        long dfs(int cur, int par, long[] x, ArrayList<Integer>[] a, HashMap<Long, Integer> h) {
            long tot = x[cur] % mod;
            HashMap<Long, Integer> t = new HashMap<>();
            for (Map.Entry<Long, Integer> e : h.entrySet()) {
                long g = func.gcd(e.getKey(), x[cur]);
                tot += (g * e.getValue()) % mod;
                t.put(g, t.getOrDefault(g, 0) + e.getValue());
            }
            t.put(x[cur], t.getOrDefault(x[cur], 0) + 1);
            for (int i : a[cur]) {
                if (i != par) {
                    tot += dfs(i, cur, x, a, t);
                    tot %= mod;
                }
            }
            return tot;
        }

    }

    static class func {
        public static long gcd(long a, long b) {
            return (b == 0) ? a : gcd(b, a % b);
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }

            while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

