/*
http://www.infoarena.ro/problema/lgput
*/

#include <fstream>
#include <iostream>
#define MOD 1999999973
using namespace std;

int main()
{
	int N, P;
	ifstream fin("lgput.in");
	fin >> N >> P;
	fin.close();

	long long solution = 1, base = N;
	//initial, base = N^(2^0) = N^1 = N
	//la fiecare pas vom avea base = N^(2^i)
	for (int i = 0; (1 << i) <= P; ++i)
	{
		//daca bitul i este 1, atunci adaug n la solutie
		if (P & (1 << i))
		{
			solution = (solution * base) % MOD;
		}

		//pregatesc base pentru a memora valoarea N^(2^(i+1))
		base = (base * base) % MOD;
	}
	ofstream fout("lgput.out");
	fout << solution << "\n";
	fout.close();
	return 0;
}