#include <iostream>
#include <fstream>

using namespace std;

const int MOD = 1999999973;

long long lgput(long long n, long long p)
{
	long long a = n; //n^(2^i)
	long long sol = 1;
	for (long long i = 0ll; (1ll << i) <= p; i++)
	{
		if ((1ll << i) & p)
			sol = (sol * a) % MOD;
		a *= a;
	}
	return (sol % MOD);
}

int main()
{
	ifstream cin("lgput.in");
	ofstream cout("lgput.out");
	long long n, p;
	cin >> n >> p;
	cout << lgput(n, p) << "\n";
	return 0;
}