#include <iostream>
#include <fstream>
#define modul 1999999973

using namespace std;
ifstream fin ("lgput.in");
ofstream fout ("lgput.out");

long int FastExp ( long int N , long int P )
{
    unsigned long int i ;
    long int bit ; long long  copie ;
    copie = N ;
    long int solutie = 1 ;
    for ( i = 0 ; ( bit = 1 << i ) <= P ; ++i )  // luam toti bitii lui P in ordine ( de la dreapta spre stanga )
        {
            if ( bit & P )  //verific daca bitul e 1 si exponentiem inca o data ;
                      solutie = (solutie * copie ) % modul ;
        copie = ( copie * copie ) % modul ;
        cout<<copie<<endl;

        }
    return solutie ;
}
int main ()
{
  long int N , P;
  fin>>N>>P;
  long int exp = FastExp (N,P) ;
  fout << exp;
  return 0;
}