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

#define MOD 1999999973


uint64_t mod(uint64_t n, uint64_t p){
  n %= MOD; // pentru n > MOD
  uint64_t rez = 1;
  while(p > 0) {  // trecem prin bitii lui p
    if(p & 1) // daca bit-ul curent e 1 
      rez = (rez * n) % MOD;
    n = (n * n) % MOD;
    p >>= 1;
  }
  return rez;
}

int main(){
  
  uint64_t N, P;

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

  if(!input || !output){
    fprintf(stderr, "Eroare deschidere fisiere!");
    exit(-1);
  }
  fscanf(input, "%lu%lu", &N, &P);
  fprintf(output, "%lu", mod(N,P)); 
  fclose(input);
  fclose(output);
  return 0;
}