#include <stdio.h>
#include <string.h>

int main()
{ 
  FILE *fp;
  int i;
  long long N,P,R;
  fp=fopen("lgput.in","r");
  fscanf(fp,"%lld%lld",&N,&P);
  fclose(fp);
  
  R=1;
  for(i=0;(1<<i)<=P;++i)
  {
     if(((1<<i)&P)>0)
        R=(R*N)%1999999973;
     N=(N*N)%1999999973;		
  }
  
  fp=fopen("lgput.out","w");
  fprintf(fp,"%lld\n",R);
  fclose(fp);
  
  return 0;
}