#include <stdio.h>
#define MOD 1999999973

using namespace std;

int main() {
    freopen ("lgput.in", "r", stdin);
    freopen ("lgput.out", "w", stdout);
    int N, P;
    scanf ("%d %d", &N, &P);
    long long a = N, sol = 1;
    for (int i = 0; (1<<i) <= P; ++i) {
        if (((1<<i) & P) > 0)
            sol = (sol * a) % MOD;
        a = (a * a) % MOD;
    }
    printf ("%lld\n", sol);
    return 0;
}