#include <stdio.h>
#define HUGE 1999999973

int putere(int baza, int exp, int acum) {
  long long bazaN, acumN;
  if(exp == 0)
    return acum;
  else {
    bazaN = (long long)baza * baza;
    bazaN = bazaN % HUGE;
    if(exp % 2 == 0)
      return putere((int)bazaN, exp / 2, acum);
    else {
      acumN = (long long)acum * baza;
      acumN = acumN % HUGE;
      return putere((int)bazaN, exp / 2, (int)acumN);
    }
  }
}

int main() {
  int n, p;
  FILE *fin = fopen( "lgput.in" , "r" );
  fscanf(fin, "%d%d", &n, &p);
  fclose( fin );

  FILE *fout = fopen( "lgput.out" , "w" );
  fprintf(fout, "%d", putere(n % HUGE, p, 1));
  fclose( fout );
  return 0;
}