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.*;
import java.util.*;
import java.util.stream.Collectors;

public class KamilStream {

    private static final long MOD = 1000000007L;

    static class Pair {
        long a;
        long b;

        public Pair(long a, long b) {
            this.a = Math.min(a, b);
            this.b = Math.max(a, b);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            if (a != pair.a) return false;
            return b == pair.b;
        }

        @Override
        public int hashCode() {
            int result = (int) (a ^ (a >>> 32));
            result = 31 * result + (int) (b ^ (b >>> 32));
            return result;
        }
    }

//    static final Map<Pair, Long> GCD_CACHE = new HashMap<>();

    static class Vertex {
        int num;
        long x;
        final List<Vertex> children = new ArrayList<>();
        Map<Long, Long> partialSums = new HashMap<>();
        Map<Long, Long> gcds = new HashMap<>();
        Vertex parent = null;

        public Vertex(int num, long x) {
            this.num = num;
            this.x = x;
        }

        @Override
        public String toString() {
            return num + ":" + children.stream().map(vertex -> Integer.toString(vertex.num)).collect(Collectors.toList()).toString();
        }
    }

    private static class VertexWithNum {
        Vertex v;
        int n;
        long cg;

        public VertexWithNum(Vertex v, int n) {
            this.v = v;
            this.n = n;
        }

        public VertexWithNum(Vertex v, int n, long cg) {
            this.v = v;
            this.n = n;
            this.cg = cg;
        }
    }

    private static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }

    public static void main(String[] args) throws FileNotFoundException {
        InputReader in = new InputReader(/*new FileInputStream("C:\\Example\\input_1.txt")*/System.in);

        int n = in.nextInt();
        Map<Integer, Vertex> graph = new HashMap<>();

        for (int i = 0; i < n; i++) {
            graph.put(i + 1, new Vertex(i + 1, in.nextLong()));
        }

        for (int i = 0; i < n - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            graph.get(a).children.add(graph.get(b));
            graph.get(b).children.add(graph.get(a));
        }

        Map<Integer, Vertex> tree = new HashMap<>();
        makeTree(graph, tree);

        System.out.println(walkTree1(tree));

    }

    private static long walkTree1(Map<Integer, Vertex> tree) {
        Stack<VertexWithNum> toVisit = new Stack<>();
        toVisit.add(new VertexWithNum(tree.get(1), 0));
        long result = processNode(tree.get(1));

        while (!toVisit.isEmpty()) {

            final VertexWithNum vertex = toVisit.peek();
            if (vertex.n == vertex.v.children.size()) {
                toVisit.pop();
            } else {
                final Vertex v = tree.get(vertex.v.children.get(vertex.n).num);
                toVisit.push(new VertexWithNum(v, 0));
                result += processNode(v);
                result %= MOD;
                vertex.n++;
            }
        }
        return result;
    }

    private static long processNode(Vertex vertex) {
        long result = vertex.x % MOD;
        vertex.gcds.put(vertex.x, 1L);
        if (vertex.parent != null) {
            for (Long gcd : vertex.parent.gcds.keySet()) {
                long newGCD = gcd(gcd, vertex.x);
                final Long count = vertex.parent.gcds.get(gcd);
                result += newGCD * count;
                if (!vertex.gcds.containsKey(newGCD)) {
                    vertex.gcds.put(newGCD, count);
                } else {
                    vertex.gcds.put(newGCD, vertex.gcds.get(newGCD) + count);
                }
                result %= MOD;
            }
        }

        return result;
    }

    private static long walkTree(Map<Integer, Vertex> tree) {
        Stack<VertexWithNum> toVisit = new Stack<>();
        toVisit.add(new VertexWithNum(tree.get(1), 0));
        long result = 0;
        while (!toVisit.isEmpty()) {

            final VertexWithNum vertex = toVisit.peek();
            if (vertex.n == vertex.v.children.size()) {
                toVisit.pop();

                long gcdForNode = 0;
                if (vertex.v.x == 0) {
                    for (Vertex child : vertex.v.children) {
                        gcdForNode += child.partialSums.get(child.x);
                        gcdForNode %= MOD;
                    }
                    vertex.v.partialSums.put(0L, gcdForNode);
                } else {
                    gcdForNode = calcGCDForNode(vertex.v.num, tree);
                }
                result += gcdForNode;
                result %= MOD;
            } else {
                toVisit.push(new VertexWithNum(tree.get(vertex.v.children.get(vertex.n).num), 0));
                vertex.n++;
            }
        }
        return result;
    }

    private static long calcGCDForNode(int vertexNum, Map<Integer, Vertex> tree) {
        Stack<VertexWithNum> toVisit = new Stack<>();
        final Vertex vv = tree.get(vertexNum);
        toVisit.add(new VertexWithNum(vv, 0, vv.x));
        Map<Integer, Long> nodePartialSums = new HashMap<>();
        long result = vv.x % MOD;
        while (!toVisit.isEmpty()) {
            final VertexWithNum vertex = toVisit.peek();
            if (vertex.n == vertex.v.children.size()) {
                toVisit.pop();
                long sum = vertex.cg;
                for (Vertex child : vertex.v.children) {
                    sum += nodePartialSums.get(child.num);
                }
                sum %= MOD;
                vertex.v.partialSums.put(vertex.cg, sum);
                nodePartialSums.put(vertex.v.num, sum);
            } else {
                final Vertex v = tree.get(vertex.v.children.get(vertex.n).num);
                long cg = gcd(v.x, vertex.cg);

                if (v.partialSums.containsKey(cg)) {
                    final Long ps = v.partialSums.get(cg);
                    result += ps;
                    nodePartialSums.put(v.num, ps % MOD);
                } else {
                    result += cg;
                    toVisit.push(new VertexWithNum(v, 0, cg));
                }
                result %= MOD;
                vertex.n++;
            }
        }
        vv.partialSums.put(vv.x, result);
        return result;
    }

    private static void makeTree(Map<Integer, Vertex> graph, Map<Integer, Vertex> tree) {
        Stack<Vertex> toVisit = new Stack<>();
        toVisit.add(new Vertex(1, graph.get(1).x));

        while (!toVisit.isEmpty()) {
            Vertex vertex = toVisit.pop();
            tree.put(vertex.num, vertex);

            for (Vertex child : graph.get(vertex.num).children) {
                if (!tree.containsKey(child.num)) {
                    final Vertex newChild = new Vertex(child.num, child.x);
                    toVisit.add(newChild);
                    vertex.children.add(newChild);
                    newChild.parent = vertex;
                }
            }
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}
