#include <fstream>
using namespace std;
int n,p;
void citire()
{
    ifstream fin ("lgput.in");
    fin>>n>>p;
    fin.close();
}
int PutereLog(int a, int n)
{
    int P=1999999973;
	int rez = 1;
	while (n > 0)
	{
		if (n % 2 == 1)
		{
			n--;
			rez = (1LL * rez * a) % P;
}
n = n/2;
a = (1LL * a * a) % P;
}
return rez;
}

int main()
{
    citire();
    ofstream fout ("lgput.out");
    fout<<PutereLog(n,p);
    fout.close();
    return 0;
}