#include <fstream>
#define mod 1999999973
using namespace std;

unsigned long long logpow(unsigned long long base, unsigned long long exponent)
{
	if (exponent == 0) return 1;
	if (exponent == 1) return base % mod;
	if (exponent % 2 == 0)
	{
		return logpow((base * base) % mod, exponent / 2) % mod;
	}
	else
	{
		return (base % mod) * (logpow((base*base) % mod, (exponent - 1) / 2) % mod) % mod;
	}
}

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

	ofstream g("lgput.out");
	g << logpow(N, P);
	g.close();
	return 0;
}