#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;
    unsigned long long base_mod = base;

    while (exp > 0)
    {
        if (exp & 1)
	  {
	    rez = (rez * base_mod) % mod;
	  }
        base_mod = (base_mod * base_mod) % 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;
}