#include <stdio.h>
#define MOD 1999999973
long long sol;
long int n,p;
void putere(){
    unsigned long int i;
    long long a;
    sol=1;
    a=n;
    for(i=0;(1<<i)<=p;i++){
        if(((1<<i)&p)>0)sol=(sol*a)%MOD;
        a=(a*a)%MOD;
    }
}

int main(){
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%ld %ld",&n,&p);
    putere();

    printf("%lld",sol);
    fclose(stdout);
    fclose(stdin);
    return 0;
}