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
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;
const LL mod=1e9+7;

LL modpow(LL x, LL n){
	LL r=1;
	while(n){
		if(n&1) r=r*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return r;
}

LL modinv(LL x){
	LL m=mod, u=1, v=0;
	while(m){
		LL t=x/m;
		x-=t*m; swap(x,m);
		u-=t*v; swap(u,v);
	}
	u%=mod;
	if(u<0) u+=mod;
	return u;
}

int main(){
  int N;
  cin >> N;
  vector<LL> A(N);
  rep(i,N) cin >> A[i];
  sort(A.begin(),A.end());
  vector<LL> Ac(N);
  rep(i,N) Ac[i]=A[i];
  LL A_Max=A[N-1];
  vector<LL> D(A_Max+1);
  rep(i,N){
    for(LL j=2; j*j<=A[i]; j++){
      int num=0;
      while(Ac[i]%j==0){
        Ac[i]/=j;
        num++;
      }
      if(D[j]<num) D[j]=num;
    }
    if(!D[Ac[i]]) D[Ac[i]]=1;
  }
  LL ans=0, lc=1;
  for(LL i=2; i<=A_Max; i++){
    lc*=modpow(i,D[i]);
    lc%=mod;
  }
  rep(i,N){
    ans+=lc*modinv(A[i]);
    ans%=mod;
  }
  cout << ans << endl;

  return 0;
}
