#include <cstdio>

#define MOD 1999999973

long long n, p, odd, rest = 1;

int main() {
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);

    scanf("%lld%lld", &n, &p);
    
    odd = n;
    while (1 < p) {
        if (1 == p % 2) {
            rest = (rest * odd) % MOD;
            --p;
        } else {
            odd = (odd * odd) % MOD;
            p /= 2;
        }
    }

    printf("%lld\n", (odd * rest) % MOD);

    return 0;
}