#include<fstream>
#define inf "lgput.in"
#define outf "lgput.out"
#define NR 1999999973
#define p2(x) ((x)*(x))
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

unsigned long long N,P;

void Citire()
{
f>>N>>P;
}

unsigned long long Putere(unsigned long long p)
{
if(p==2)return N*N;
else
    {
    if(p%2==0)return p2(Putere(p/2));
    else
        {
        return p2(Putere((p-1)/2))*N;
        }
    }
}

int main()
{
Citire();
g<<Putere(P)%NR;
f.close();
g.close();
return 0;
}