/*
 * lgput.cpp
 *
 *  Created on: Mar 2, 2012
 *      Author: Tibi
 */
#define DEBUG 1
#define MAGIC 1999999973

#if DEBUG==1
#include <iostream>
#warning Debug is ON
#endif

#include <fstream>
using namespace std;
int main()
{
	ifstream in ("lgput.in");
	ofstream out ("lgput.out");

	long long n, p, sol = 1;

	in>>n>>p;

	for (int i = 0; (1<<i) <= p; i++)
	{
		if (p & (1<<i)) sol = (sol * n) % MAGIC;
		n = (n * n) % MAGIC;
	}

#if DEBUG==1
	cout<<sol;
#endif
	out<<sol;

	in.close();
	out.close();
	return 0;
}