#include <cstdio>
int main(){
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	int a,b,i,masca=1,lg;
	scanf("%d %d",&a,&b);
	//aflam dimensiunea puterii b in baza 2
	for (i=0 ; i<=31 ; i++)
		if ((masca<<i)&b)lg=i+1;
	//lungimea e buna
	long long pow=1;
	for( i=lg ; i>=0 ; i-- ){
		pow=(pow*pow)%1999999973;
		if( (masca<<i) & b )pow=(pow*a)%1999999973;
	}
	printf("%lld",pow);
}