int@A,@B,@N;
int P[10000001];
const int md1 = 1d9+7;
const int md2 = md1 - 1;
rep(x, 1, B + 1) {
    P[x] = powmod(B/x - (A-1)/x, N, md2);
}
rrep(x, 1, B + 1) {
    int t = 0;
    rep(y, x + x, B + 1, x) if(P[y]>0) {
        t += P[y];
        if(t >= md2) t -= md2;
    }
    P[x] -= t;
    if(P[x] < 0) P[x] += md2;
}
ll ans = 1;
rep(x, 1, B + 1) if(P[x] > 0) {
    ans *= powmod(x, P[x], md1);
    ans%=md1;
}
wt(ans);