#include<stdio.h>   
#define M 1999999973
long long v[40];
int main(){
	long long n,p,sol=1,i;
    freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	v[0]=n;
    for(i=1;((long long)1<<i)<=p;i++)
		v[i]=(v[i-1]*v[i-1])%M;
	for(i=1;((long long)1<<i)<=p;i++)
		if((1<<i)&p)
			sol=(sol*v[i])%M;
    printf("%lld\n",sol);
	fclose(stdin);
	fclose(stdout);
	return 0;
}