#include <stdio.h>

#define MODULO 1999999973

long ExpLogRec(long x, long n, long modulo) {
  if (n < 0) {
    return 1 / ExpLogRec(x, -n, modulo);
  } else if (n == 0) {
    return 1;
  } else if (n % 2 == 0) {
    long temp = ExpLogRec(x, n / 2, modulo);
    return (temp * temp) % modulo;
  } else if (n % 2 == 1) {
    long temp = ExpLogRec(x, (n - 1) / 2, modulo);
    return (x * temp * temp) % modulo;
  }
  return 0;
}

int main() {
  //freopen("lgput.in","r",stdin);
  //freopen("lgput.out","w",stdout);
  long nr = 0, exp = 0;
  scanf("%ld%ld", &nr, &exp);
  long modulo = MODULO;
  printf("%ld", ExpLogRec(nr, exp, modulo));
  return 0;
}