#include<iostream.h>
#include<fstream.h>
long long n,p,i=0,k,x1,x2;
int v[100000];
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%1999999973)*(x2%1999999973))%1999999973;
     x1=((x1%1999999973)*(x1%1999999973))%1999999973;}
else
     {x1=((x1%1999999973)*(x2%1999999973))%1999999973;
     x2=((x2%1999999973)*(x2%1999999973))%1999999973;}
f2<<x1%1999999973;
f1.close();
f2.close();
return 0;}