#include <iostream>
#include <fstream>
using namespace std;

//int e_012_lgput()
int main()
{
	char in_file[] = "lgput.in";
	char out_file[] = "lgput.out";

	unsigned int N, P;
	unsigned int a = 1999999973;

	const int max_powers = 33;

	ifstream ifs(in_file);
	ifs>>N>>P;
	ifs.close();

	//processing
	unsigned int R = N%a;//the remainder of N to a; R^P instead of N^P

	//the desired powers
	int powers1[max_powers];
	int powers2[max_powers];

	int ind_powers = 0;
	int P1 = P, P1_;
	while (P1 != 0)
	{
		
		P1_ = P1;//save the old P1
		P1 /= 2;
		powers1[ind_powers] = P1;
		powers2[ind_powers] = P1_ - P1;//the difference between powers1[k] and powers2[k] is at most 1
		
		ind_powers++;
	}

	unsigned int res1 = 1, res2;
	for (int i = ind_powers-1; i >= 0 ; i--)
	{
		if (powers2[i] > powers1[i]) res2 = (res1*R)%a;
		else res2 = res1;

		res1 = (res1*res2)%a;		
	}

	ofstream ofs(out_file);
	ofs<<res1;
	ofs.close();

	return 0;
}