#include <cstdio>
int f[10000];
int main () {
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	unsigned long long int a,b,i,p=1,k;
	scanf("%lld %lld",&a,&b);
	for(i=1;b!=0;++i){
		f[i]=b%2;
		b=b/2;
	}
	i--;
	k=i;
	for(i=k;i>=1;--i){
		if(f[i]==1){
			p=((p%1999999973)*(p%1999999973)*(a%1999999973))%1999999973;
		}
		else {
			p=((p%1999999973)*(p%1999999973))%1999999973;
		}
	}
	printf("%lld",p);
}