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

#define MOD 1999999973

int put(int a, unsigned int p){
  int valret;
  if(0 < p){
    valret = put(a, p / 2);
    if((p % 2) == 1){
      valret = ((long long)((long long)a * valret) % MOD * valret) % MOD;
    }else{
      valret = ((long long)valret * valret) % MOD;
    }
  }else{
    valret = 1;
  }
  return valret;
}

int main()
{
    FILE *fin, *fout;
    unsigned int n, p;
    fin=fopen("lgput.in", "r");
    fscanf(fin, "%u%u", &n, &p);
    fclose(fin);
    fout=fopen("lgput.out", "w");
    fprintf(fout, "%d", put(n % MOD, p));
    fclose(fout);
    return 0;
}