#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 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;
}