LOJ124 sigma sum

#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 10000010, PC = 2000000, P = 1000000007;

int n, k, pc;
bool f[N];
int sigma[N], minp[N], pw[N], p[PC];

int pow(int a, int k);

int main() {
    int ans = 0;
    scanf("%d%d", &n, &k);
    sigma[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!f[i]) {
            p[++pc] = i;
            minp[i] = i;
            pw[i] = sigma[i] = pow(i, k);
            if (++sigma[i] >= P)
                sigma[i] = 0;
        }
        for (int j = 1; i * p[j] <= n; ++j) {
            int ind = i * p[j];
            if (i % p[j]) {
                f[ind] = true;
                minp[ind] = p[j];
                sigma[ind] = (ll) sigma[i] * sigma[p[j]] % P;
            } else {
                f[ind] = true;
                minp[ind] = minp[i] * p[j];
                if (i == minp[i]) {
                    sigma[ind] = ((ll)sigma[i] * pw[i] % P);
                    if (++sigma[ind] >= P)
                        sigma[ind] = 0;
                    pw[ind] = pw[i];
                }
                else
                    sigma[ind] = (ll) sigma[i / minp[i]] * sigma[minp[ind]] % P;
                break;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans += sigma[i];
        if (ans >= P)
            ans -= P;
    }
    printf("%d\n", ans);
    return 0;
}

inline int pow(int a, int k) {
    int ret = 1;
    while (k) {
        if (k & 1)
            ret = (ll) ret * a % P;
        a = (ll) a * a % P;
        k >>= 1;
    }
    return ret;
}