#include <stdio.h>
#include <stdlib.h>

int main(){
  FILE*fin=fopen("lgput.in", "r");
  FILE*fout=fopen("lgput.out", "w");
  long long x, n, p;
  fscanf(fin, "%lld%lld", &n, &p);
  x=n;
  while(p>1){
    if(p%2==0){
      x=x*x;
      p/=2;
      x%=1999999973;
    }
    else{
      x=x*(x*x);
      p=(p-1)/2;
      x%=1999999973;
    }
  }
  fprintf(fout, "%lld", x);
  return 0;
}