#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=0;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;
}