#include <cstdio>

#define N_MOD 1999999973

long long lgput(long long n, long long p, long long m) {
  if(!p)
    return 1;
  if(p & 1)
    return (lgput(n * n % m, p >> 1, m) % m) * (n % m) % m;
  else
    return lgput(n * n % m, p >> 1, m) % m;
}

int main(void) {

  long long n, p;

  FILE *in = fopen("lgput.in", "r");
  FILE *out = fopen("lgput.out", "w");

  fscanf(in, "%lld%lld", &n, &p);

  fprintf(out, "%lld\n", lgput(n, p, N_MOD));

  return 0;
}