看第一篇题解打的，但是数组需要开成原来两倍才能过.

看别人都是开了 $10^5$ 的数组就过了，特此求问.

80pts:

把下面 sqrtn 的值改成 $10^5$，会发现连样例 3 都过不了.

100pts:

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   mod=1000000007;
const int   inv3=333333336;
const int   inv2=500000004;
const int   sqrtn=200000;
bool        flag[sqrtn+10];
int         w[2*sqrtn+10],sum1[2*sqrtn+10],sum2[2*sqrtn+10];
int         pri[sqrtn+10],psum1[sqrtn+10],psum2[sqrtn+10];
int         idxl[sqrtn+10],idxr[sqrtn+10];
int         n,pnum,tot;

void linear()
{
    flag[1]=true;
    for(int i=2; i<=sqrtn; i++)
    {
        if(!flag[i])
        {
            pri[++pnum]=i;
            psum1[pnum]=(psum1[pnum-1]+i)%mod;
            psum2[pnum]=(psum2[pnum-1]+i*i%mod)%mod;
        }
        for(int j=1; j<=pnum&&pri[j]*i<=sqrtn; j++)
        {
            flag[i*pri[j]]=true;
            if(i%pri[j]==0)
                break;
        }
    }
    return;
}

void init()
{
    for(int i=1; i<=n; )
    {
        int next=(n/(n/i));
        tot++;
        w[tot]=n/i%mod;
        sum1[tot]=w[tot]*(w[tot]+1)%mod*inv2%mod;// Cal i
        sum2[tot]=w[tot]*(w[tot]+1)%mod*inv2%mod*(2*w[tot]%mod+1)%mod*inv3%mod;// Cal i*i
        sum1[tot]--,sum2[tot]--;// Except 1
        w[tot]=n/i;
        if(n/i<=sqrtn)
            idxl[n/i]=tot;
        else
            idxr[next]=tot;
        i=next+1;
    }
    return;
}

void part1()
{
    for(int i=1; i<=pnum; i++)
        for(int j=1; j<=tot&&pri[i]*pri[i]<=w[j]; j++)
        {
            int temp=(w[j]/pri[i]<=sqrtn? idxl[w[j]/pri[i]]:idxr[n/(w[j]/pri[i])]);
            sum1[j]-=pri[i]*(sum1[temp]-psum1[i-1]+mod)%mod;
            sum2[j]-=pri[i]*pri[i]%mod*(sum2[temp]-psum2[i-1]+mod)%mod;
            sum1[j]=(sum1[j]%mod+mod)%mod;
            sum2[j]=(sum2[j]%mod+mod)%mod;
        }
    return;
}

int part2(int p,int k)
{
    if(pri[k]>=p)
        return 0;
    int temp=(p<sqrtn? idxl[p]:idxr[n/p]);
    int tar=(((sum2[temp]-sum1[temp])-(psum2[k]-psum1[k]))%mod+3*mod)%mod;// Prime
    for(int i=k+1; i<=pnum&&pri[i]*pri[i]<=p; i++)
    {
        int pmi=pri[i];
        for(int e=1; pmi<=p; e++,pmi=pmi*pri[i])
        {
            int temp2=pmi%mod;
            tar+=temp2*(temp2-1)%mod*(part2(p/pmi,i)+(int)(e!=1))%mod;
        }
    }
    return tar%mod;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    /* Code */
    cin>>n;
    linear();
    init();
    part1();
    cout<<(part2(n,0)%mod+1)%mod<<'\n';
    return 0;
}