#include <cstdio>

int main(){
	long long sol=1,a=1;
	unsigned int n,p,i;
	freopen("lgput.in","rt",stdin);
	freopen("lgput.out","wt",stdout);
	scanf("%d%d",&n,&p);
	a=n;
	for(i=0;(1<<i)<p;i++,a=a*a%1999999973)
		if(p&(1<<i))
			sol=(sol*a)%1999999973;
	
	printf("%lld",(long long)sol%1999999973);	
}