#include<fstream>
using namespace std;
unsigned long long n,p,m,z,r,c;
int main()
{
   ifstream f("lgput.in");
   ofstream g("lgput.out");
    f>>n>>p;
    c=1999999973;
    m=n%c;
    z=1;
    while(p!=0)
     {
         r=p%2;
         if(r==1)
         {
             z=(z*m)%c;
         }
       m=(m*m)%c;
       p=p/2;
     }
    g<<z;
    g.close();
    f.close();
    return 0;
}