// scriem n^p = suma(n^(2^i)), unde bitul i al lui n este nenul
#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 long i,sol=1,a;
 a=n;
 for (i=0;(1<<i)<=p;++i)
  {
   if ((1<<i)&p) sol=(sol*a)%MODULO;
   a=(a*a)%MODULO;
  }

 FILE *fout=fopen("lgput.out","w");
 fprintf(fout,"%lld\n",sol);
 fclose(fout);
 return 0;
}