#include<fstream.h>

ifstream fin("lgput.in");
ofstream fout("lgput.out");
const int n_max=10001;//definim numarul maxim de cifre al numerelor
const int m=1999999973;
int main()
{
	unsigned int i,n,p;
	long long a,sol=1;
	fin>>n>>p;
	a=n;
	for(i=0;(1<<i)<=p;i++)	// luam toti biti lui p la rand
	{
		if(((1<<i)&p)>0)// daca bitui i din p este 1 atunci adaugam n^(2^i) la solutie
			sol=(sol*a)%m;
		a=(a*a)%m;// inmultim a cu a ca sa obtinem n^(2^i+1);
	}
	fout<<sol<<'\n';
	return 0;
}