#include <cstdio>
int v[100000000];
int main(){
        freopen("lgput.in","r",stdin);
        freopen("lgput.out","w",stdout);
        unsigned long long A,B=1,pow;
        unsigned long long i,j;
        scanf("%lld %lld",&pow,&B);
        A=1;
        for(i=1;B!=0;i++){
                v[i]=B%2;
                B/=2;
        }
        i--;
        for(j=i;j>0;--j){
                A=(A*A)%1999999973;
                if(v[j]==1){
                        A=(A*pow)%1999999973;
                }
        }
        printf("%d",A);
}