B-ArrayGCD

#include <bits/stdc++.h>
#define mod 666013
using namespace std;
int power(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2 == 1) {
        return (1ll * a * power(a, b - 1)) % mod;
    }
    int P = power(a, b / 2);
    return (1ll * P * P) % mod;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> dp(m + 1ll);
    dp[m] = 1;
    for (int i = m - 1ll; i >= 1; --i) {
        dp[i] = power(m / i, n);
        for (int j = 2 * i; j <= m; j += i) {
            if (dp[j] > dp[i]) {
                dp[i] = dp[i] - dp[j] + mod;
            }
            else {
                dp[i] = dp[i] - dp[j];
            }
        }
    }
    int sum = 0;
    for (int i = 1; i <= m; ++i) {
        sum += (1ll * dp[i] * i) % mod;
        if (sum >= mod) {
            sum -= mod;
        }
    }
    cout << sum;
}