#include<stdio.h>
long long N,K,M,rez;
int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%lld%lld",&N,&K);
    M=N;
    rez=1;
    for(int i=0;1LL*(1<<i)<=K;++i)
    {
        if((1<<i)&K)
        {//printf("%d\n",i);
            rez*=M;
            rez%=1999999973;
        }
        M*=M;
        M%=1999999973;

    }
    printf("%lld",rez);
}