#include<iostream.h>
#include<fstream.h>
long long n,p,i=0,v[10000],y[10000],x1,x2,j,k,t;
int main()
{ifstream f1("lgput.in");
ofstream f2("lgput.out");
f1>>n>>p;
while(p!=0)
     {v[i++]=p%2;
     p/=2;}
x1=n;
x2=n*n;
for(k=i-2;k>=0;k--)
if(v[k]==0)
     {x2=(x1*x2)%1999999973;
     x1=(x1*x1)%1999999973;}
else
     {x1=(x1*x2)%1999999973;
     x2=(x2*x2)%1999999973;}
f2<<x1%1999999973;
f1.close();
f2.close();
return 0;}