#include<fstream>
#include<vector>
#define m 1999999973

using namespace std;

ifstream in("lgput.in");
ofstream out("lgput.out");

int main()
{
	vector<unsigned long long> puteri,putere;
	unsigned int n,p,i=1,put;
	unsigned long long rez=1;
	puteri.resize(32);
	in>>n>>p;
	puteri.at(0)=n;
	while(p)
	{
		i=0;
		put=p-(p&(p-1));
		p=p&(p-1);
		while(put>>1) put>>=1,i++;
		putere.push_back(i);
	}
	for(i=1;i<=putere.at(putere.size()-1);i++) puteri.at(i)=(puteri.at(i-1)*puteri.at(i-1))%m;
	for(i=0;i<putere.size();i++)
		rez=(rez*puteri.at(putere.at(i)))%m;
	out<<rez;
}