#include <cstdio>
#define MOD 1999999973

int pow(int x, int P);

int main()
{
    int n, p;

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

    scanf("%d %d", &n, &p);
    printf("%d", pow(n, p));
}

int pow(int x, int P){
    x %= MOD;
    if (P>=1){
        int r = pow(x, P/2);
        if (P%2){
            return (((long long)r*(long long)r)*x)%MOD;
        }
        else{
            return ((long long)r*(long long)r)%MOD;
        }
    }
    return 1;
}