#include <stdio.h>
#define mod 1999999973
unsigned long i,n,p,v[33],q;
unsigned long long pow;
int main()
{
    FILE*f1,*f2;
    f1=fopen("lgput.in","r");
    f2=fopen("lgput.out","w");
    fscanf(f1,"%lu%lu",&n,&p);
    pow=n;
    v[1]=n;
    if(p==0)
    {
        fprintf(f2,"%lu",1);
        return 0;
    }
    for(i=1;i<p;)
    {
        pow=(pow*pow)%mod;
        v[i]=pow;
        i*=2;
    }
    if(p==i)
        fprintf(f2,"%llu",pow);
    else
    {
        p-=(i/2);
        for(;p;i/=2)
            while(p>=i)
            {
                p-=i;
                pow*=v[i];
            }
        fprintf(f2,"%llu",pow);
    }
    return 0;
}