Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

* 1 \leq N \leq 10^4
* 1 \leq A_i \leq 10^6
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 ... A_N


Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Examples

Input

3
2 3 4


Output

13


Input

5
12 12 12 12 12


Output

5


Input

3
1000000 999999 999998


Output

996989508
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
		    a[i] = sc.nextInt();
		}
		
		// 計算
		long result = 0;
		int MOD = 1000000007; 
		Prime p = new Prime(1000000);
		HashMap<Integer, Integer> mapAll = new HashMap<Integer, Integer>();
		for(int i = 0; i < n; i++){
		    HashMap<Integer, Integer> map = p.factorization(a[i]);
		    for(Integer key : map.keySet()){
		        mapAll.put(key, max(mapAll.getOrDefault(key, 0), map.get(key)));
		    }
		}
		//System.out.println(mapAll.toString());
		long lcm = 1;
		for(Integer key : mapAll.keySet()){
		    lcm *= pow(key, mapAll.get(key), MOD);
		    lcm %= MOD;
		}
		
		for(int i = 0; i < n; i++){
		    result += lcm*inv(a[i], MOD);
		    result %= MOD;
		}
		
		// 出力
		System.out.println(result);
	}

	public static long pow(long a, long n, long MOD) {
	    long res=1;
	    while (n>0) {
	        if ((n-n/2*2)==1) {
	            res=(res*a)%MOD;
	        }
	        a=(a*a)%MOD;
	        n>>=1;
	    }
	    return res%MOD;
	}

	public static long inv(long a, long MOD) {
	    return pow(a, MOD - 2, MOD);
	}
	
}

class Prime {
    int n;
    ArrayList<Integer> primes;
    int[] seive;
    
    public Prime(int n){
        this.n = n;
        int[] seive = new int[n+1];
        Arrays.fill(seive, -1);
        ArrayList<Integer> primes = new ArrayList<Integer>();
        for(int i = 2; i <= n; i++){
            if(seive[i] != -1) continue;
            primes.add(i);
            seive[i] = i;
            for(long j = (long)i*i; j <= n; j += i){
                if(seive[(int)j] == -1) seive[(int)j] = i; 
            }
        }
        this.seive = seive;
        this.primes = primes;
    }
    
    public boolean isPrime(int x){
        return seive[x] == x;
    }
    
    public HashMap<Integer, Integer> factorization(int x){
        HashMap<Integer, Integer> factorization = new HashMap<Integer, Integer>();
        ArrayList<Integer> factorList = factorList(x);
        if(factorList.size() == 0) return factorization;
        for(Integer i : factorList){
            int cnt = factorization.getOrDefault(i, 0);
            factorization.put(i, cnt + 1);
        }
        return factorization;
    }
    
    private ArrayList<Integer> factorList(int x){
        ArrayList<Integer> factorList = new ArrayList<Integer>();
        while(x != 1){
            factorList.add(seive[x]);
            x /= seive[x];
        }
        return factorList;
    }
    
}

