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