#include<stdio.h>
#define N 1999999973
unsigned int f(int n, int p){
	if(p==0) return 1;
	if (p==1) return n%N;
	int x=f(n,p/2);
	return (unsigned int)(((long long)x*(long long)x%(long long)N)*(long long)f(n, p%2)%(long long)N);
}

int main(){
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);
	int n, p;
	scanf("%d", &n);
	scanf("%d", &p);
	n=n%N;
	p=p%(N-1);
	printf("%d\n", f(n, p));
	return 0;
}