#include<fstream.h>

unsigned long  n;

unsigned long hatvany(unsigned long x){
	unsigned long s;
	if(x==1)
		return n;
	else
		s=hatvany(x/2);
		if(x%2==0)
		       return s*s%1999999973;
		else
			return s*s*n%1999999973; }

int main(void) {
	ifstream f("lgput.in");
	ofstream g("lgput.out");
	unsigned long p;
	f>>n>>p;
	g<<hatvany(p)%1999999973;    }