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 <cstring>
#include <iostream>
#define MOD 1000000007
using namespace std;
int a[10005],f[1000005],lf[1000005],n;
long long lcm=1;
long long fpow(long long x,long long y){
 long long ans=1;
 while(y){
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
void calc(int x){
 memset(f,0,sizeof(f));
 int x1=x;
 for(int i=2;x!=1&&i*i<=x1;i++){
  while(x%i==0)
   x/=i,f[i]++;
  lf[i]=max(lf[i],f[i]);
 }
 if(x!=1){
  f[x]++;
  lf[x]=max(lf[x],f[x]);
 }
}
int main(){
 cin>>n;
 for(int i=1;i<=n;i++){
  cin>>a[i];
  calc(a[i]);
 }
 long long ans=0;
 for(int i=2;i<=1e6;i++)
  lcm=lcm*fpow(i,lf[i])%MOD;
 for(int i=1;i<=n;i++)
  ans=(ans+lcm*fpow(a[i],MOD-2))%MOD;
 cout<<ans<<endl;
}