#include<cstdio>

int cif[100];

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