#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) // inca merge unsigned int pt limitele problemei
{
  unsigned long long rez = 1;
  
  while ( exp > 0 )
    {
      if ( exp & 1 ) {
	rez = ( rez * base ) % mod;
      }
      base = ( base * 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;
}