#include<fstream>
using namespace std;
#define m 1999999973
int main()
{
	unsigned int i,n,p;
	long long a,sol=1;//pt ca e produs
	ifstream fin("lgput.in");
	fin>>n>>p;
	fin.close();
	a=n;
	for(i=0;(1<<i)<=p;++i)//luam toti biti lui p la rand
    {
		if(((1<<i)&p)>0)//daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
			sol=(sol*a)%m;//facem %m ca sa nu depaseasca long long
        a=(a*a)%m;//inmultim a cu a ca sa obtinem n^(2^(i+1))
    }
	FILE *fout=fopen("lgput.out");
	fprintf(fout,"%lld",sol);
	return 0;
}