#include<fstream>
using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");
const int ma=1999999973;
const long long nr=1<<32;
long long v[35],n,p,i,q,j,q1;

int main ()
{
	in>>n>>p;
	v[1]=n;
	i=1;
	q=1;
	do
	{
		v[++i]=(v[i-1]*v[i-1])%ma;
		q*=2;
	}
		while(q<=p);
	v[i]=0;
	i--;
	j=1;
	q/=2;
	q1=q;
	j=i;
	while(q1<p)
	if(q1+q/2<=p)
		{
			v[++i]=(v[i-1]*v[j-1])%ma;
			j--;
			q1=q1+q/2;
			q=q/2;
		}
	else
	{
		q/=2;
		j--;
	}
	out<<v[i];
}