#include <stdio.h>
#define C 1999999973

unsigned long long n,p;

int main(){
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	scanf("%lld %lld",&n,&p);
	unsigned long long put =1;
	for (int i = 0; (1<<i) <= p ; i++){
		if(( (1<<i) & p ) > 0 )
			put *= n;
	n*=n;
		
	}
	printf("%lld",put%C);
	return 0;
}