题解

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1000000007;
LL p[20], k[20], ans, a[20][40], n;

int cnt;
inline LL qpow(LL a, LL b) {
    LL re=1;
    for(;b;b>>=1,a=a*a%mod)if(b&1)re=re*a%mod;
    return re;
}
void dfs(int i, LL x, LL phi) {
    if(i > cnt) {
        if(x < n)
            ans = (ans + 1ll * qpow(2, x) * phi % mod) % mod;
        return;
    }
    for(int j = 0; j <= k[i]; ++j)
        dfs(i+1, x*a[i][j], phi/a[i][j]/(j<k[i]?p[i]:1)*(j<k[i]?p[i]-1:1)); 
}
int main () {
    cin>>n; LL N = n;
    for(LL i = 2; i*i <= n; ++i)
        if(n % i == 0) {
            p[++cnt] = i;
            a[cnt][0] = 1;
            while(n % i == 0) {
                n /= i, ++k[cnt];
                a[cnt][k[cnt]] = a[cnt][k[cnt]-1] * i;
            }
        }
    if(n > 1) p[++cnt] = n, k[cnt] = 1, a[cnt][0] = 1, a[cnt][1] = n;
    n = N;
    dfs(1, 1, n);
    cout<<((ans - n + 2) % mod + mod) % mod<<'\n'; 
}