#include <cstdio>
int v[100000000];
int main(){
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	unsigned long long A,B=1,pow;
	unsigned long long i,j;
	scanf("%lld %lld",&pow,&B);
	A=1;
	for(i=1;B!=0;i++){
		v[i]=B%2;
		B/=2;
	}
	i--;
	for(j=i;j>0;--j){
		A*=A%1999999973;
		if(v[j]==1){
			A*=pow%1999999973;
		}
	}
	printf("%d",A);
}