#include <stdio.h>

#define nr 1999999973

long long n,p,rez;

int main()
{

	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	rez=n%nr;
	--p;
	while(p>1)
		{
			if(p%2==1)
				{
					rez=(rez*n)%nr;
					--p;
				}
			else
				{
					rez=(rez*rez)%nr;
					p/=2;
				}
		}
	printf("%lld",rez);
	return 0;
}