Description
去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。
在整理以前的试题时，发现了这样一道题目“求Sigma(f(i)),其中1<=i<=N”，其中 表示i的约数个数。他现在长大了，题目也变难了。
求如下表达式的值：
其中 表示ij的约数个数。
他发现答案有点大，只需要输出模1000000007的值。
Input
第一行一个整数n。
Output
一行一个整数ans，表示答案模1000000007的值。
Sample Input
2
Sample Output
8
HINT
对于100%的数据n <= 10^9。
#include<cstdio>
#include<cctype>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
typedef long long ll;
const int SIZE=1000000;
const int mod=1000000007;
bool vis[SIZE+10];
int mu[SIZE+10],pri[SIZE/10],cnt;
void init(int n) {
vis[1]=mu[1]=1;
rep(i,2,n) {
if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
rep(j,1,cnt) {
if(i*pri[j]>n) break;
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
rep(i,2,n) mu[i]+=mu[i-1];
}
map<int,int> M;
int getmu(int n) {
if(n<=SIZE) return mu[n];
if(M.count(n)) return M[n];
int ans=1;
rep(i,2,n) {
int last=n/(n/i);
ans=(ans-(ll)(last-i+1)*getmu(n/i)%mod+mod)%mod;
i=last;
}
return M[n]=ans;
}
int getf(int n) {
int ans=0;
rep(i,1,n) {
int last=n/(n/i);
(ans+=(ll)(n/i)*(last-i+1)%mod)%=mod;
i=last;
}
return (ll)ans*ans%mod;
}
int main() {
int n=read();init(1000000);
ll ans=0;
rep(i,1,n) {
int last=n/(n/i);
(ans+=(ll)getf(n/i)*(getmu(last)-getmu(i-1)+mod))%=mod;
i=last;
}
printf("%lld
",ans);
return 0;
}