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

#define REST 1999999973

long long exp_log_rec(long long N, long long P)
{
  if(P < 0)
    {
      return exp_log_rec(1.0 / N, -P);
    }
  else if(P == 0)
    {
      return 1;
    }
  else if(P % 2 == 0)
    {
      return exp_log_rec(N*N, P/2);
    }
  else if(P % 2 == 1)
    {
      return N * exp_log_rec(N*N, P/2);
    }
  return 0;
}

int main(void)

{
  long long N, P, result;
  FILE *fin;
  FILE *fout;

  if((fin = fopen("lgput.in","r"))==NULL)
    {
      printf("Eroare deschidere fisier\n");
      exit(-1);
    }

  if((fout = fopen("lgput.out","w"))==NULL)
    {
      printf("Eroare deschidere fisier\n");
      exit(-1);
    }

  fscanf(fin,"%lld %lld", &N, &P);

  result = exp_log_rec(N, P) % REST;

  fprintf(fout,"%lld\n", result);

  fclose(fin);
  fclose(fout);

  return 0;

}