C++

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define pb(a) push_back(a)
#define pr(a,b) make_pair(a,b)
#define f first
#define s second

const ll md = 1e9+7;

ll pw(ll b, ll e) {ll a=1; while (e>0) {if (e&1){a=a*b%md;} b=b*b%md; e>>=1;} return a;}
ll inv(ll a){return pw(a, md-2);}

ll rng_sum(int n) {
    return 1LL*n*(n+1)%md*inv(2)%md;
}

ll solve(int n) {
    ll ans = 0;
    vector<ll> dp(n+1);
    for (int i = n; i >= 1; i--) {
        int m = n/i;
        dp[i] = 1LL*pw(i,2)*pw(rng_sum(m),2)%md;
        for (int j = i+i; j <= n; j+=i) {
            dp[i] = ((dp[i]-dp[j])%md+md)%md;
        }
        ans = (ans+dp[i]*inv(i)%md)%md;
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    cout << solve(n) << "\n";
}

Consider this subproblem: You're given a positive integer \(N\). Consider every pair of integers (\(x, y\)) such that (\(1 \le x, y \le N\)). You're asked, for each number \(i\) from \(1\) to \(N\), how many pairs (\(x, y\)) are there such that gcd(\(x, y\)) = \(i\)?