#include<stdio.h>
#include<values.h>
FILE *f1,*f2;
long long v[33]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4292967296};
long long a,n,p,put[33];
long i,j;
int s[33];
int main(){
	f1=fopen("lgput.in","r");
	f2=fopen("lgput.out","w");
	fscanf(f1,"%lld%lld",&n,&p);
	j=0;
	for(i=32;i>=0;i--){
		if(a+v[i]<=p){
			j++;
			s[j]=i;
			a=a+v[i];
		}
	}
	a=n%1999999973;
	for(i=1;i<=s[1];i++){
		put[i]=a;
		a=(a*a)%1999999973;
	}
	a=1;
	for(i=1;i<=j;i++){
		a=(a*put[s[i]])%1999999973;
	}
	fprintf(f2,"%lld",a);
	return 0;
}