#include <stdio.h>

class TLogPower
{
   public:
      TLogPower(long long lldModulo);

      unsigned long long Power(long long lldNumber, long long lldExp);
   private:
   protected:
      long long m_lldModulo;
};

//----------------------------------------
unsigned long long  TLogPower::Power(long long lldNumber, long long lldExp)
{
   if (lldExp == 1) return lldNumber; else
   if (lldExp % 2 == 0) return (Power(lldNumber,lldExp / 2) % m_lldModulo)*(Power(lldNumber,lldExp / 2) % m_lldModulo) % m_lldModulo; else
   if (lldExp % 2 == 1) return (Power(lldNumber,lldExp - 1)*lldNumber) % m_lldModulo;
}
//----------------------------------------
TLogPower::TLogPower(long long lldModulo)
{
   this->m_lldModulo=lldModulo;
}
//----------------------------------------
      unsigned long long Power(long long llExp);
//----------------------------------------
//----------------------------------------
//----------------------------------------
//----------------------------------------
void ReadData(long long* lldNumber, long long* lldExp)
{
   FILE * fIn = fopen("lgput.in","r");

   fscanf(fIn,"%lld %lld", lldNumber, lldExp);

   fclose(fIn);
}
//----------------------------------------
int main()
{
    long long lldNumber, lldExp;
    ReadData(&lldNumber,&lldExp);

    FILE * fOut = fopen ("lgput.out","w");

    TLogPower * objPower = new TLogPower(1999999973);

    fprintf(fOut,"%lld\n", objPower->Power(lldNumber,lldExp)); // Afisam solutia

    fclose(fOut);
}