Codeforces Round #818 (Div. 2)

E. Madoka and The Best University

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Madoka wants to enter to "Novosibirsk State University", but in the entrance exam she came across a very difficult task:

Given an integer nn, it is required to calculate ∑lcm(c,gcd(a,b))∑lcm⁡(c,gcd(a,b)), for all triples of positive integers(a,b,c), where a+b+c=n.

In this problem gcd(x,y) denotes the greatest common divisor of x and y, and lcm(x,y) denotes the least common multiple of x and y.

Solve this problem for Madoka and help her to enter to the best university!

Input

The first and the only line contains a single integer nn (3≤n≤10^5).

Output

Print exactly one interger — ∑lcm⁡(c,gcd(a,b)). Since the answer can be very large, then output it modulo 109+7.

Examples

input

3

output

1

input

5

output

11

input

69228

output

778304278

Note

In the first example, there is only one suitable triple (1,1,1) So the answer is lcm(1,gcd(1,1))=lcm(1,1)=1.

In the second example, lcm(1,gcd(3,1))+lcm(1,gcd(2,2))+lcm(1,gcd(1,3))+lcm(2,gcd(2,1))+lcm(2,gcd(1,2))+lcm(3,gcd(1,1))=lcm(1,1)+lcm(1,2)+lcm(1,1)+lcm(2,1)+lcm(2,1)+lcm(3,1)=1+2+1+2+2+3=11

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N = 1e5+5;
int phi[N], p[N], cnt;
vector<int>G[N];
int n;
bool vis[N];//为1即为合数，为0则为质数
void getphi(int n)
{
    phi[1] = 1;
    for (int i=2; i<=n; i++)
    {
        if (!vis[i]) p[++cnt]=i,phi[i]=i-1;
        for (int j=1; j<=cnt&&i*p[j]<=n; j++)
        {
            vis[i*p[j]]=1;
            if (i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else phi[i*p[j]]=phi[i] * phi[p[j]];
        }
    }
    phi[1]=0;
}
ll lcm(ll x,ll y)
{
    return x*y/__gcd(x,y);
}
void getdiv()
{
    for(int i=1;i<N;i++)
    {
        for(int j=i;j<N;j+=i)
        {
            G[j].push_back(i);
        }
    }
}
void solve()
{
    int n;
    cin>>n;
    ll ans = 0;
    getdiv();
    for(int c=1; c<n; c++)
    {
        for(auto x:G[n-c])
        {
            ans = (ans+(ll)lcm(c, x)*(ll)phi[(n-c)/x]%mod)%mod;
        }
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
     getphi(1e5);
     solve();
 
 
    return 0;
}

 n*logn*logn

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N = 1e5+5;
int phi[N], p[N], cnt;
int n;
bool vis[N];//为1即为合数，为0则为质数
void getphi(int n)
{
    phi[1] = 1;
    for (int i=2; i<=n; i++)
    {
        if (!vis[i]) p[++cnt]=i,phi[i]=i-1;
        for (int j=1; j<=cnt&&i*p[j]<=n; j++)
        {
            vis[i*p[j]]=1;
            if (i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else phi[i*p[j]]=phi[i] * phi[p[j]];
        }
    }
    phi[1]=0;
}
ll lcm(ll x,ll y)
{
    return x*y/__gcd(x,y);
}
vector<int>factors(int n)
{
    set<int>s;
    for(int i=1; i<=sqrt(n); i++)
    {
        if(n%i==0) s.insert(i);
        if(n%i==0&&i!=n/i) s.insert(n/i);
    }
    return vector<int>(s.begin(),s.end());
}
void solve()
{
    int n;
    cin>>n;
    ll ans = 0;
    for(int c=1; c<n; c++)
    {
        for(int d:factors(n-c))
        {
            ans = (ans+(ll)lcm(c, d)*(ll)phi[(n-c)/d]%mod)%mod;
        }
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
     getphi(1e5);
     solve();
 
 
    return 0;
}

n*sqrt(n)*logn