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


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

#include <fstream>
using namespace std;

long long res[64];

long long solve (long long pow)
{
	if (pow < 3) return res[pow];

	long long i = 0;
	while ((1<<i) < pow ) i++;

	if (1<<i == pow) return res[i+1];
	else return (res[i+1] * solve(pow - (1<<i))) % 1999999973;
}

int main()
{
	ifstream in ("lgput.in");
	ofstream out ("lgput.out");
	long long n, p, pleft;
	long long i;

	in>>n>>p;

	res[0] = 1;
	res[1] = n;

	for (i = 1; (1<<i) <= p; i++)
		res[i+1] = res[i] * res[i] % 1999999973;
	pleft = p - (1<<(i - 1));

	out<<(res[i] * solve(pleft)) % 1999999973;
#if DEBUG==1
	cout<<res[i] * solve(pleft);
#endif

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