\(\mathcal{Description}\)

  Link.

  积性函数 \(f\) 满足 \(f(p^c)=p\oplus c~(p\in\mathbb P,c\in\mathbb N_+)\)，求 \(\sum_{i=1}^n f(i)\bmod(10^9+7)\)。

\(\mathcal{Solution}\)

  首先，考虑 \(f\) 的素数点值：

\[f(p)=\begin{cases}
3,&p=2\\
p-1,&\text{otherwise}
\end{cases}
\]

由 \(p-1\) 联想到 \(\varphi(p)=p-1\)，可惜 \(\varphi(2)=1\)。干脆一点，我们直接强行把 \(\varphi\) 的偶数点值乘上 \(3\)，令

\[g(n)=\begin{cases}
\varphi(n),&2\not\mid n\\
3\varphi(n),&\text{otherwise}
\end{cases}
\]

显然它也是积性函数。

  接着，求 \(g\) 的前缀和。其前缀和为 \(\varphi\) 的前缀和加上两倍偶数点的 \(\varphi\) 前缀和。记

\[\begin{aligned}
S(n)&=\sum_{i=1}^n\varphi(2i)\\
&=\sum_{i=1}^n[2\not\mid i]\varphi(i)+2\sum_{i=1}^n[2\mid i]\varphi(i)\\
&=S\left(\frac{n}{2}\right)+\sum_{i=1}^n\varphi(i)
\end{aligned}
\]

杜教筛处理 \(\varphi\) 的前缀，\(S\) 就能在可观（我不会算 qwq）的复杂度内预处理出来，继而也得到了 \(g\) 的 \(\mathcal O(\sqrt n)\) 个前缀和。

  此外，我们还需要求 \(h(i)\)，即求 \(h(p^c)~(c>1)\)。考虑 \(f(p^c)\) 与它的关系：

\[f(p^c)=\sum_{i=0}^ch(p^i)g(p^{c-i})\\
\Rightarrow~~~~h(p^c)=f(p^c)-\sum_{i=0}^{c-1}h(p^i)g(p^{c-i})
\]

顺手把 \(\mathcal O(\sqrt n\ln\ln\sqrt n)\)（\(n\) 以内素数的倒数和的规模是 \(\mathcal O(\ln\ln n)\)）个 \(h(p^c)\) 也预处理出来，最后 \(\mathcal O(\sqrt n)\) 搜索 Powerful Number 就能求出答案啦！

/* Clearink */

#include <cmath>
#include <cstdio>
#include <vector>
#include <unordered_map>

#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )
#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )

typedef long long LL;

const int MAXS = 1e7, MAXSN = 1e5, MOD = 1e9 + 7, INV2 = 500000004;
int pn, pr[MAXS + 5], phi[MAXS + 5], phis[MAXS + 5];
bool npr[MAXS + 5];
std::vector<int> gpr[MAXSN + 5];

inline int mul( const long long a, const int b ) { return a * b % MOD; }
inline int sub( int a, const int b ) { return ( a -= b ) < 0 ? a + MOD : a; }
inline void subeq( int& a, const int b ) { ( a -= b ) < 0 && ( a += MOD ); }
inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline void addeq( int& a, const int b ) { ( a += b ) >= MOD && ( a -= MOD ); }

inline void sieve() {
    phi[1] = phis[1] = 1;
    rep ( i, 2, MAXS ) {
        if ( !npr[i] ) phi[pr[++pn] = i] = i - 1;
        for ( int j = 1, t; j <= pn && ( t = i * pr[j] ) <= MAXS; ++j ) {
            npr[t] = true;
            if ( !( i % pr[j] ) ) { phi[t] = phi[i] * pr[j]; break; }
            phi[t] = phi[i] * ( pr[j] - 1 );
        }
        phis[i] = add( phis[i - 1], phi[i] );
    }
}

inline int phiSum( const LL n ) {
    static std::unordered_map<LL, int> mem;
    if ( n <= MAXS ) return phis[n];
    if ( mem.count( n ) ) return mem[n];
    int ret = mul( mul( n % MOD, ( n + 1 ) % MOD ), INV2 );
    for ( LL l = 2, r; l <= n; l = r + 1 ) {
        r = n / ( n / l );
        subeq( ret, mul( ( r - l + 1 ) % MOD, phiSum( n / l ) ) );
    }
    return mem[n] = ret;
}

inline int ephiSum( const LL n ) {
    if ( !n ) return 0;
    return add( ephiSum( n >> 1 ), phiSum( n ) );
}

LL n;
int sn, sum[MAXSN * 2 + 5];

inline void initInvG() {
    rep ( i, 1, pn ) {
        if ( 1ll * pr[i] * pr[i] > n ) break;
        std::vector<int>& curg( gpr[i] );
        curg.push_back( 1 ), curg.push_back( 0 );
        LL pwr = 1ll * pr[i] * pr[i];
        for ( int j = 2; pwr <= n; ++j, pwr *= pr[i] ) {
            int g = pr[i] ^ j;
            LL pwc = pr[i];
            for ( int k = j - 1; ~k; --k, pwc *= pr[i] ) {
                subeq( g,
                    mul( ( pwc / pr[i] * ( pr[i] ^ 1 ) ) % MOD, curg[k] ) );
            }
            curg.push_back( g );
        }
    }
}

inline int powerSum( const int pid, LL x, const int g ) {
    if ( !g ) return 0;
    int ret = 0, p = pr[pid];
    if ( pid == 1 || !( x % pr[pid - 1] ) ) {
        addeq( ret, mul( g, x > sn ? sum[n / x] : sum[sn + x] ) );
    }
    if ( ( x *= p ) > n ) return ret;
    if ( ( x *= p ) > n ) return ret;
    addeq( ret, powerSum( pid + 1, x / ( 1ll * p * p ), g ) );
    for ( int i = 2; x <= n; ++i, x *= p ) {
        addeq( ret, powerSum( pid + 1, x, mul( g, gpr[pid][i] ) ) );
    }
    return ret;
}

int main() {
    sieve();
    scanf( "%lld", &n ), sn = sqrt( 1. * n );
    rep ( i, 1, sn ) sum[i] = add( phiSum( i ), mul( 2, ephiSum( i >> 1 ) ) );
    rep ( i, 1, sn ) {
        sum[i + sn] = add( phiSum( n / i ), mul( 2, ephiSum( n / i >> 1 ) ) );
    }
    initInvG();
    printf( "%d\n", powerSum( 1, 1, 1 ) );
    return 0;
}