#include <cstdlib>
#include <cstdio>
FILE*f;
FILE*g;


int main()
{
    int n,p,i;
    long long x,q;
    f=fopen("lgput.in","r");
    g=fopen("lgput.out","w");
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&p);
    
    x=1;
    q=n;
    for (i=0;(1<<i)<=p;++i)
        {
             if (((1<<i)&p)>0)
                x=(x*q)%1999999973;
             q=(q*q)%1999999973;
        }
    fprintf(g,"%d",x);
    return 0;
}