#include <stdio.h>
#define MODULO 1999999973
unsigned long n,p;


void citire()
{
 FILE *fin=fopen("lgput.in","r");
 fscanf(fin,"%ld %ld",&n,&p);
 fclose(fin);
}

int main()
{
 citire();
 n%=MODULO;
 unsigned long i,y,z;
 i=p; y=1; z=n;
 while (i!=0)
  {
   if (i%2) y=(y*z)%MODULO;
   z=(z*z)%MODULO;
   i>>=1;
  }
 FILE *fout=fopen("lgput.out","w");
 fprintf(fout,"%ld\n",y);
 fclose(fout);
 return 0;
}