#include <iostream>
#include <fstream>

using namespace std;

#define TERM 1999999973

ifstream fin("lgput.in");
ofstream fout("lgput.out");

int X, P;

void read(void)
{
	fin >> X >> P;
}

long long int exp_by_squaring(long long int x, long long int n)
{
	if (n < 0)
	{
		exp_by_squaring(1 / x, -n);
	}
	else if (n == 0)
	{
		return 1;
	}
	else if (n % 2 == 0)
	{
		return exp_by_squaring((x * x) % TERM, n / 2);
	}
	else if (n % 2 != 0)
	{
		return (x * exp_by_squaring((x * x) % TERM, (n - 1) / 2) ) % TERM;
	}
}

void print(void)
{
	fout << exp_by_squaring(X, P);
}

int main(void)
{
	read();
	print();
	return 0;
}