#include<stdio.h>

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

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("%lu",prod);

	return 0;
}