#include "stdio.h"

FILE *f=fopen("lgput.in","r");
FILE *g=fopen("lgput.out","w");
long x=1999999973;
long n;
long hatvany(long b);

int main()
{
	long p;
	fscanf(f,"%ld%ld",&n,&p);
	long meg=hatvany(p);
	fprintf(g,"%ld",meg%x);
	fclose(f);
	fclose(g);
	return 0;
}

long hatvany(long b)
{
	if(b==1)return n;
	long c=hatvany(b/2);
	if(b%2) return (n*c*c)%x;
	return (c*c)%x;
}