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<stdio.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#define rep(i,N) for(int i=0;i<(int)N;i++)
const int MOD=1e9+7;
int A[10000];
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline int MPow(int a,int b){return b?1l*MPow(1l*a*a%MOD,b>>1)*(b&1?a:1)%MOD:1;}
int count(const int prime,const int sz)
{
  int max=0;rep(i,sz){int now=0;while(A[i]%prime==0){now++;A[i]/=prime;}if(max<now)max=now;}return max;
}
int main(void)
{
  int N=IN(),x=0,p=1,q=-1;
  rep(i,N){A[i]=IN();x=(x+1l*MPow(A[i],MOD-2))%MOD;}
  x=1l*x*MPow(2,count(2,N))%MOD;
  x=1l*x*MPow(3,count(3,N))%MOD;
  while(q*q<=1e6)
  {
    p+=6,q+=6;
    x=1l*x*MPow(p,count(p,N))%MOD;
    x=1l*x*MPow(q,count(q,N))%MOD;
  }
  rep(i,N){if(A[i]>1){rep(j,N-1-i){if(A[i]==A[i+j+1]){A[i+j+1]=1;}}x=1l*x*A[i]%MOD;}}
  return printf("%d\n",x),0;
}