#include<stdio.h>

unsigned long n,p,i;
long long prod,a;
long x;

int main()
{
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);

	scanf("%lu %lu",&n,&p);

	x=1999999973;

	a=n;

	prod=1;

	for(i=0;(1<<i)<=p;i++)
	{
	       if((1<<i)&p)
		       prod=(prod*a)%x;
	       a=(a*a)%x;
	}

	printf("%lld\n",prod);

	return 0;
}