#include <bits/stdc++.h>

#define MOD 1999999973

using namespace std;

long long N, P, answer = 1;

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

    scanf("%lld%lld", &N, &P);

    for (int pow = 0; (1 << pow) <= P; ++pow) {
        if ((1 << pow) & P) {
            answer = answer * N % MOD;
        }

        N = (N * N) % MOD;
    }

    printf("%lld", answer);

    fclose(stdin);
    fclose(stdout);

    return 0;
}