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.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class Task {
    	public static final long Mod=(long) (1e9+7);
    	public long ans=0;
    	public long[] x;
    	public ArrayList<Integer>[] edge;
    	
    	public long gcd(long a,long b) {
    		if(a<b) {
    			long temp=a;
    			a=b;
    			b=temp;
    		}
    		
    		while(b>0) {
    			long c=a%b;
    			a=b;
    			b=c;
    		}
    		
    		return a;
    	}
    	
    	public void dfs(int u,int fa,HashMap<Long,Integer> map) {
    		HashMap<Long,Integer> nowBuf=new HashMap<Long,Integer>();
    		nowBuf.put(x[u], 1);
    		ans+=x[u];
    		ans%=Mod;
    		for(Map.Entry<Long, Integer> temp:map.entrySet()) {
    			long g=gcd(x[u],temp.getKey());
    			ans+=g*temp.getValue();
    			ans%=Mod;
    			int d=temp.getValue();
    			if(nowBuf.containsKey(g))
    				d+=nowBuf.get(g);
    			nowBuf.put(g, d);
    		}
    		for(int v:edge[u]) {
    			if(v==fa)
    				continue;
    			dfs(v,u,nowBuf);
    		}
    	}
    	
        public void solve(int testNumber, InputReader sc, PrintWriter out) throws IOException {
        	int n=sc.nextInt();
        	edge=new ArrayList[n+1];
        	x=new long[n+1];
        	
        	for(int i=1;i<=n;i++)
        		edge[i]=new ArrayList<Integer>();       //因为一条链上的gcd只有log(x)个   x是这条链上的最小元素？
        	for(int i=1;i<=n;i++) {
        		x[i]=sc.nextLong();
        	}
        	for(int i=1;i<n;i++) {
        		int u=sc.nextInt();
        		int v=sc.nextInt();
        		edge[u].add(v);
        		edge[v].add(u);
        	}
        	HashMap<Long,Integer> map=new HashMap<Long,Integer>();
        	dfs(1,-1,map);
        	out.println(ans);
        }

    }

    static class InputReader {
        private InputStreamReader reader;
        private char[] buf;
        private int len, now;
     
        public InputReader(InputStream stream) {
            reader = new InputStreamReader(stream);
            buf = new char[1024];
            len = 0;
            now = 0;
        }
     
        public String next() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            StringBuilder sb = new StringBuilder();
            while (!isSpaceChar(buf[now])) {
                sb.append(buf[now]);
                if (!move()) break;
            }
            return sb.toString();
        }
     
        public int nextInt() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            boolean x = false;
            if (buf[now] == '-') {
                x = true;
                if (!move()) throw new NumberFormatException();
            }
            int ans = 0;
            while (!isSpaceChar(buf[now])) {
                if (isNum(buf[now])) ans = ans * 10 + buf[now] - '0';
                else throw new NumberFormatException();
                if (!move()) break;
            }
            return (x ? -1 : 1) * ans;
        }
     
        public String nextLine() throws IOException {
            if (!hasNextLine()) throw new NullPointerException();
            StringBuilder sb = new StringBuilder();
            while (buf[now] != '\n') {
                sb.append(buf[now]);
                if (!move()) return sb.toString();
            }
            now++;
            return sb.toString();
        }
     
        public long nextLong() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            boolean x = false;
            if (buf[now] == '-') {
                x = true;
                if (!move()) throw new NumberFormatException();
            }
            long ans = 0;
            while (!isSpaceChar(buf[now])) {
                if (isNum(buf[now])) ans = ans * 10 + buf[now] - '0';
                else throw new NumberFormatException();
                if (!move()) break;
            }
            return (x ? -1 : 1) * ans;
        }
     
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
     
        public int nextHexInt() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            boolean x = false;
            if (buf[now] == '-') {
                x = true;
                if (!move()) throw new NumberFormatException();
            }
            int ans = 0;
            while (!isSpaceChar(buf[now])) {
                if (isHex(buf[now])) ans = ans * 16 + toHex(buf[now]);
                else throw new NumberFormatException();
                if (!move()) break;
            }
            return (x ? -1 : 1) * ans;
        }
     
        public char nextChar() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            char tmp = buf[now];
            move();
            return tmp;
        }
        public int next(char[] s) throws IOException {
            if (!hasNext()) throw new NullPointerException();
            int len=0;
            while (!isSpaceChar(buf[now])&&len<s.length) {
                s[len++]=buf[now];
                if (!move()) break;
            }
            return len;
        }
        public boolean hasNext() throws IOException {
            return skip();
        }
     
        public boolean hasNextLine() throws IOException {
            return now < len || refill();
        }
     
        private boolean move() throws IOException {
            now++;
            return hasNextLine();
        }
     
        private boolean skip() throws IOException {
            if (!hasNextLine()) return false;
            while (isSpaceChar(buf[now])) {
                if (!move()) return false;
            }
            return true;
        }
     
        private boolean isSpaceChar(char c) {
            return !(c >= 33 && c <= 126);
        }
     
        private boolean isNum(char c) {
            return c >= '0' && c <= '9';
        }
     
        private boolean isHex(char c) {
            return c >= '0' && c <= '9' || c >= 'A' && c <= 'F';
        }
     
        private int toHex(char c) {
            if (c >= '0' && c <= '9') return c - '0';
            else return c - 'A' + 10;
        }
     
        private boolean refill() throws IOException {
            len = reader.read(buf);
            now = 0;
            return len > 0;
        }
    }
}
