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> 
#define rg register 
#define fp( i , x , y ) for( rg int i=(x); i<=(y); ++i ) 
#define fq( i , x , y ) for( rg int i=(y); i>=(x); --i ) 
#define i60 long long 
#define dou double  
#define ls k<<1 
#define rs k<<1|1 
using namespace std ; 
const int N = 1e5+10 , mod=1e9+7 ; 
int n , a[N] , pri[N] , len , vi[N] , phi[N] , lis[N] , sz[N] , cnt[N] ; 
vector <int> v[N] ; 
i60 nw ; 
void prep( int m ) { 
  phi[1]=1 ; 
  fp( i , 2 , m ) { 
    if( !vi[i] ) { 
      vi[i] = i ; pri[++len] = i ; 
      phi[i] = i-1 ; 
	} 
	fp( j , 1 , len ) { 
	  if( i*pri[j] > m || pri[j] > vi[i] ) break ; 
	  vi[i*pri[j]] = pri[j] ; 
	  phi[pri[j]*i] = phi[i] * ( i%pri[j] ? pri[j]-1 : pri[j] ) ;  
	} 
  } 
  fp( i , 1 , m ) { 
    for(int j=i; j<=m; j+=i) v[j].push_back(i) ; 
    sz[i] = v[i].size() ;  
  } 
} 
void add( int x , int z ) { 
  int j ; 
  fp( i , 1 , sz[x] ) { 
    j = v[x][i-1] ; 
    if( z==1 ) nw -= 1ll * cnt[j] * cnt[j] * phi[j] ; 
	cnt[j] += z ;  
    if( z==1 ) nw += 1ll * cnt[j] * cnt[j] * phi[j] ; 
  } 
  nw %= mod ; 
} 
i60 solve( ) { 
  nw=0 ; 
  fp( i , 1 , len ) add( lis[i] , 1 ) ; 
  i60 tp=nw ; 
  fp( i , 1 , len ) add( lis[i] , -1 ) ; 
  return tp ;  
} 
signed main( ) { 
  ios::sync_with_stdio(false) ; 
  cin.tie(0) ; 
  cin >> n ; int m=0 ; 
  fp( i , 1 , n ) cin >> a[i] , m=max( m , a[i] ) ;  
  prep( m ) ; i60 ans=0 ; 
  fp( i , 1 , n ) { 
    len=0 ;  
    for(int j=i; j<=n; j+=i) lis[++len]=a[j] ; 
    ans += 1ll*phi[i]*(solve()%mod)%mod ; 
  } 
  cout << ans%mod << '\n' ; 
  return 0 ; 
} 
/*

4
4 2 2 4



*/