#include <stdio.h>
#define GNT 1999999973

long long Sol;
long N,P,v[35],i,pow;

int main()
{
	freopen("lgput.in","r",stdin);
	scanf("%ld%ld",&N,&P);
	Sol=N;
	pow=0;
	while(P>1)
	{
		v[++pow]=P%2;
		P/=2;
	}
	for(i=pow;i>0;i--)
	{
		Sol*=Sol;
		Sol%=GNT;
		if(v[i]==1) Sol*=N;
		Sol%=GNT;
	}
	freopen("lgput.out","w",stdout);
	printf("%lld\n",Sol);
	return 0;
}