#include<stdio.h>
#define MODULO 1999999973
long long int N,P,SOL;
void deschidere()
{
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
}
void citire()
{
	scanf("%lld%lld",&N,&P);
}
void ridicare(long long int X,long long int Y)
{
	if(Y!=1)
		if(Y%2)
		{
			ridicare(X,Y-1);
			SOL=(SOL%MODULO) * (X%MODULO);
		}
		else
		{
			ridicare (X,Y/2);
			SOL=(SOL%MODULO) * (SOL%MODULO);
		}
}
int main()
{
	deschidere();
	citire();
	int X=N,Y=P;SOL=N;
	ridicare(X,Y);
	printf("%lld",SOL);
	return 0;
}