#include <cstdio>

const long long int m = 1999999973;

int main(){

  unsigned i, p;
  long long int a, sol;
  int x, n;

  freopen("lgput.in", "r", stdin);
  freopen("lgput.out", "w", stdout);

  scanf("%d %d", &x, &n);

  a = x; sol = 1;
  for(i = 0; (1<<i) <= p; i++){
    if(((1<<i) & p) > 0)
      sol = (sol*a) % m;

    a = (a*a) % m;
  }
  printf("%lld\n", sol);

  return 0;
}