#include <stdio.h>

#define NUMBER_MAX 1999999973

int main() {
  freopen("lgput.in","r",stdin);
  freopen("lgput.out","w",stdout);
  long long numar, putere;
  scanf("%lld%lld", &numar, &putere);
  numar %= NUMBER_MAX;
  long long result = 1;
  while (putere) {
    if (putere % 2 == 1) {
      result = result * numar % NUMBER_MAX;
      putere -= 1;
    } else {
      numar = numar * numar % NUMBER_MAX;
      putere /= 2;
    }
  }
  printf("%lld\n", result);
  return 0;
}