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

#define MOD 1999999973
#define FILE_IN "lgput.in"
#define FILE_OUT "lgput.out"

// pb lgput de pe infoarena

// e teorie

unsigned int tl_mod(unsigned int base, unsigned int exp, unsigned int mod)
{
    unsigned long long rez = 1;

    while (exp > 0)
    {
        if (exp & 1)
	  {
            rez = (rez * base) % mod;
	  }
        base = ( base * base ) % mod;  // Calculăm pătratul lui base_mod
        exp >>= 1;
    }

    return ( unsigned int ) rez;
}

/*
int tl_mod ( int x, int n, int M )
{
  long long MM=0LL;
  MM+=M;
  long long ret=1LL, acc=0LL;
  acc+=x;
  for(int i=1;i<=n;i*=2){
    if((i&n)){
      ret*=acc;
      if(ret>=MM){
	ret%=MM; 
      }
    }
    acc*=acc;
    if(acc>=M){
      acc%=M;
    }
  }
  return ((int)ret);
}
*/


int main ( void )
{
  FILE *fin, *fout;
  fin = fopen ( FILE_IN, "r" );
  fout = fopen ( FILE_OUT, "w" );
  if ( fin == NULL || fout == NULL )
    {
      perror ( "Eroare la deschidere fisiere\n" );
      exit ( -1 );
    }

  unsigned int n, p;
  fscanf ( fin, "%u %u", &n, &p );
  
  unsigned int rez = tl_mod ( n, p, MOD );
  fprintf ( fout, "%u\n", rez );
  
  if ( ( fclose ( fin ) ) != 0 || ( fclose ( fout ) ) != 0 )
    {
      perror ( "Eroare la inchidere fisiere\n" );
      exit ( -2 );
    }
  return 0;
}