#include <cstdio>
#define mod 1999999973
long long a[64];
int main()
{
	long long n,p;
	freopen("lgput.in","r",stdin);
	scanf("%lld %lld", &n, &p);
	
	long long sol=1;
	int i;
	a[0]=n;
	for(i=1;i<=32;++i)
		a[i]=a[i-1]*a[i-1],a[i]%=mod;
	
	for(i=0;i<=32;++i)
		if(p&(1LL<<i))
		{
			sol*=a[i], sol%=mod;
		}
	
	
	freopen("lgput.out","w",stdout);
	printf("%lld\n",sol);
	
	return 0;
}