#include <fstream>


using namespace std;
#define MOD 1999999973;

int pow(int a, int b)
{
	int c=1;
	for(int i=0; i<b; i++)
		c=c*a;
	return c;
}


int exp(int N, int P)
{
	int b=1, EXP=1;

	for(int i=0; i<32; i++)
	{
		if(P&1)
			EXP*=(pow(N, (P&1)*b)) % MOD;
		P=P>>1;
		b*=2;

	}
	return EXP;
}


int main()
{
	int N, P;

	ifstream fin("lgput.in");
	fin>>N>>P;
	fin.close();

	ofstream fout("lgput.out");
	fout<<exp(N, P);
	fout.close();

	return 0;


}