#include<iostream>
#include<fstream>
using namespace std;
int putere_binara(int baza,long long int expo)
{
	int i;
	//baza%=n;
	int b[50],nrb=0;
	for(;expo;expo/=2)
		b[++nrb]=expo%2;
	int rez=1;
		for(i=nrb;i;i--)
		{
			rez*=rez;
			if(b[i])
				rez*=baza;
		}
		return rez;
}
int main()
{
	ifstream fin("lgput.in");
	ofstream fout("lgput.out");
	int baza;
	long long int expo;
		fin>>baza>>expo;
		fout<<putere_binara(baza,expo)%1999999973;
		return 0;
}