#include <iostream>
#include <fstream>
#define x 1999999973
using namespace std;
long long n, p, i, k;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
int main()
{
	fin >> n >> p;
	k = n;
	while (p)
	{
		while ( p % 2 == 0 )
		{
			p /= 2;
			n = n * n;
			n = n % x;
		}
		while (p % 3 == 0)
		{
			p /= 3;
			n = n * n * n;
			n = n % x;
		}
		while (p % 5 == 0)
		{
			p /= 5;
			n = n * n * n * n * n;
			n = n % x;
		}
	}
	for (i = 1; i <= p; i++)
	{
		n = n * k;
		n = n % x;
	}
	fout << n;
	return 0;
}