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


long long exponent_log(long long x, long long n)
{
  
  if(n == 0)
    {
      return 1;
    }
 
  if(n % 2 == 0)
    {
      return exponent_log(x*x, n/2);
    }
 
  else //if(n % 2 == 1)
    {
      return x * exponent_log(x*x, n/2);
    }
}

int main ()
{
  long long n = 0;

  long long p = 0;

  long long exponentiala = 0;

  FILE *file_in = NULL;
  FILE * file_out = NULL;

  if((file_in = fopen("lgput.in","r")) == NULL)
    {
      perror("EROARE LA DESCHIDEREA FISIERULUI DE CITIRE !");
      exit(-1);
    }

  if((file_out = fopen("lgput.out","w")) == NULL)
    {
      perror("EROARE LA DESCHIDEREA FISIERULUI DE SCRIERE !");
      exit(-1);
    }

  fscanf(file_in,"%lld",&n);

  fscanf(file_in,"%lld",&p);
  

  exponentiala = exponent_log(n,p);

  fprintf(file_out,"%lld",exponentiala % 1999999973);
  
  
  fclose(file_in);

  fclose(file_out);
  
  
  return 0;
}