题目链接：LOJ
题目大意：从前有个积性函数 $f$ 满足 $f(1)=1,f(p^k)=p\oplus k$。（异或）求其前 $n$ 项的和对 $10^9+7$ 取模的值。
$1\le n\le 10^{10}$。
这种奇怪但是简洁的积性函数求和，首选 min_25 筛。
首先可以发现，对于质数 $p$，$p\ge 3$ 时 $f(p)=p-1$，$p=2$ 时 $f(p)=p+1$。
所以可以先把 $f(2)$ 看做 $1$，这样方便处理 $g$，最后计算 $S$ 时再加个 $2$ 就好了。
至于 min_25 筛的具体流程，打个广告
时间复杂度 $O(\frac{n^{3/4}}{\log n})$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=,mod=,inv2=;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
int sq,pri[maxn],pl,tot,id1[maxn],id2[maxn],g0[maxn],g1[maxn],s1[maxn];
bool vis[maxn];
ll n,w[maxn];
inline int add(int a,int b){return a+b<mod?a+b:a+b-mod;}
inline int sub(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int id(ll x){return x<=sq?id1[x]:id2[n/x];}
inline int pre1(ll x){return add(sub(g1[id(x)],g0[id(x)]),x>=?:);}
inline int pre2(ll x){return add(sub(s1[x],x),x?:);}
void init(){
sq=sqrt(n);
FOR(i,,sq){
if(!vis[i]) pri[++pl]=i,s1[pl]=add(s1[pl-],i);
FOR(j,,pl){
if(i*pri[j]>sq) break;
vis[i*pri[j]]=true;
if(i%pri[j]==) break;
}
}
for(ll l=,r;l<=n;l=r+){
r=n/(n/l);
w[++tot]=n/l;
if(n/l<=sq) id1[n/l]=tot;
else id2[n/(n/l)]=tot;
int x=w[tot]%mod;
g0[tot]=sub(x,);
g1[tot]=sub(mul(mul(x,x+),inv2),);
}
}
void calc_g(){
FOR(i,,pl) FOR(j,,tot){
if((ll)pri[i]*pri[i]>w[j]) break;
g0[j]=sub(g0[j],sub(g0[id(w[j]/pri[i])],i-));
g1[j]=sub(g1[j],mul(pri[i],sub(g1[id(w[j]/pri[i])],s1[i-])));
}
}
int solve(ll nn,int x){
if(pri[x]>=nn) return ;
int ans=sub(pre1(nn),pre2(x));
FOR(i,x+,pl){
if((ll)pri[i]*pri[i]>nn) break;
ll pro=;
FOR(j,,){
pro*=pri[i];
if(pro>nn) break;
ans=add(ans,mul(pri[i]^j,add(j!=,solve(nn/pro,i))));
}
}
return ans;
}
int main(){
scanf("%lld",&n);
init();
calc_g();
printf("%d\n",add(,solve(n,)));
}