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<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1e9+7;
const int maxn = 1e4+5;
ll a[maxn];
int p[1000005];
ll inv[1000005];
void getinv()
{
	inv[1] = 1;
	for(int i=2;i<1000005;i++)
	{
		inv[i] = (ll)(mod - mod/i)*inv[mod%i]%mod;
		inv[i] = (inv[i]%mod+mod)%mod;
		//cout<<inv[i]<<" ";
	}
}

int main()
{
	int n;
	getinv();
	while(cin>>n)
	{
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			int tmp = a[i];
			for(int j=2;j*j<=a[i];j++)
			{
				int cnt = 0;
				while(tmp%j==0)
				{
					tmp/=j;
					cnt++;
				}
				if(cnt > p[j])
				{
					p[j] = cnt;
				}
				//if(cnt>0) cout<<j<<" "<<cnt<<" ";
			}
			if(tmp>=2) 
			{
				p[tmp] = max(1,p[tmp]);
			}
		}
		ll lcm = 1;
		for(int i=0;i<1000005;i++)
		{
			if(p[i]>0)
			{
				lcm = lcm*pow(i,p[i]);
				lcm%=mod;
			}
			
		}//cout<<lcm<<"\n";
		ll ans = 0;
		for(int i=1;i<=n;i++)
		{
			ans+=lcm*inv[a[i]]%mod;
			ans=(ans%mod+mod)%mod;
		} 
		cout<<ans<<"\n";
	}
}
/*
5
1000000 999999 999998 999997 999996
*/