#include <stdio.h>

int k = 1999999973;
 
int main()
{
	FILE* f1,*f2;
	f1=fopen("lgput.in","r");
	f2=fopen("lgput.out","w");
    unsigned int i, n, p,nr;
    long long sol = 1;
 
   
    fscanf(f1,"%d %d", &n, &p);
    for(int i=128;i>=0;i--)
	{
		if((p>>i)&1==1)
		{
			nr=i;
			break;
		}
	}

	long long x=1;
	for(int i=nr;i>=0;i--)
	{
		x=(x*x)%k;
		if((p>>i)&1==1)
			sol=(sol*n)%k;
	}
	fprintf(f2,"%lld\n",sol);
}