#include <fstream>
using namespace std;

ifstream fi ("lgput.in");
ofstream fo ("lgput.out");

const long long MOD = 1999999973;
long long N, P;

long long lgput (long long e)
{
	if (e == 1) return N;
	long long x = lgput (e / 2);
	if (e & 1) return (x * x * N) % MOD;
	return (x * x) % MOD;
}

int main ()
{
	fi >> N >> P;
	fo << lgput (P);	
	return 0;
}