#include <fstream>
using namespace std;

int main(void)
{
 fstream fin("lgput.in",ios::in);
 fstream fout("lgput.out",ios::out);
 long long N,P,C,R,T;
 C = 1999999973;
 fin >> N >> P;
 R = 1;
 T = N;
 while (P > 0)
  {
   T = (T * N) % C;
   if (P & 1)
     {
      R = (R * T) % C;
     }
   P = P >> 1;
  }
 fout << R;
 fin.close();
 fout.close();
 return 0;
}