Mr. Chanek has an array a of n integers. The prettiness value of a is denoted as:

$$$∑_{i=1}^{n} {∑_{j=1}^{n} {\gcd(a_i, a_j) ⋅ \gcd(i, j)}}$$$

where \gcd(x, y) denotes the greatest common divisor (GCD) of integers x and y.

In other words, the prettiness value of an array a is the total sum of \gcd(a_i, a_j) ⋅ \gcd(i, j) for all pairs (i, j).

Help Mr. Chanek find the prettiness value of a, and output the result modulo 10^9 + 7!

Input

The first line contains an integer n (2 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^5).

Output

Output an integer denoting the prettiness value of a modulo 10^9 + 7.

Example

Input


5
3 6 2 1 4


Output


77
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10,S=320,mod=1e9+7;
int pri[N],miu[N],phi[N],cnt,f[N];
bool np[N];
vector<int> ds[N];
void sieve(int n){
	phi[1]=miu[1]=1;
	for(int i=2;i<=n;++i){
		if(!np[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
			np[i*pri[j]]=1;
			if(!(i%pri[j])){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			miu[i*pri[j]]=-miu[i];
			phi[i*pri[j]]=phi[i]*phi[pri[j]];
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;j+=i)
			ds[j].push_back(i),f[j]+=i*miu[j/i];
}

int n,m,a[N],c[N];
ll ans=0;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i],m=max(m,a[i]);
	sieve(m);
	int q=sqrt(n);
	for(int d=1;d<=q;++d){
		memset(c,0,sizeof(c));
		ll sum=0;
		for(int i=d;i<=n;i+=d)
			for(int j:ds[a[i]])++c[j];
		for(int i=1;i<=m;++i)
			sum+=c[i]*c[i]*phi[i];
		ans=(ans+sum%mod*f[d])%mod;
	}
	for(int d=q+1;d<=n;++d){
		ll sum=0;
		for(int i=d;i<=n;i+=d)
			for(int j=d;j<=n;j+=d)
				sum+=__gcd(a[i],a[j]);
		ans=(ans+sum%mod*f[d])%mod;
	}
	cout<<ans<<endl;
}