#include<fstream>
using namespace std;
long long n,k,p,c,y,z,x,r;
fstream fin,fout;
int main()
{
    fin.open("lgput.in",ios::in);
    fout.open("lgput.out",ios::out);
    fin>>n>>p;
    x=p;
    c=1999999973;
    z=n%c;
    y=1;
    while(x>0)
    {
        r=x%2;
        if(r==1)
        {
            y=(y*z)%c;
        }
        x=x/2;
        z=(z*z)%c;
    }
    fout<<y;
    fin.close();
    fout.close();
    return 0;
}