#include <cstdio>
using namespace std;
long long n,p,px,r,rez;
int main()
{
	FILE* f=fopen("lgput.in","r");
	FILE* g=fopen("lgput.out","w");
	fscanf(f,"%d %d",&n,&p);
	px=p;
	rez=1;
	while (n)
	{
		r=n%2;
		if (r)
			rez*=px;
		rez=rez%1999999973;
		px*=px;
		px=px%1999999973;
		n/=2;
	}
	
	fprintf(g,"%d\n",rez);
	fclose(f);
	fclose(g);
	return 0;
}