#include<stdio.h>

long long a,sol,p,i;
long long m=1999999973;

int main()
{
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	scanf("%lld%lld",&a,&p);
	sol=1;
	for (i = 0; (1<<i) <= p; ++ i)  // Luam toti biti lui p la rand  
	{ 
		if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie  
		sol= (sol * a) % m; 
		a=(a * a) % m; // Inmultim a cu a ca sa obtinem n^(2^(i+1)) 
	} 
   
	printf("%lld\n", sol); // Afisam solutia 


	
	
	return 0;	

}