// infoarenaDFSnonRec.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>

#define MOD 1999999973

using namespace std;

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

int N, P;

int main() {
	fin >> N >> P;
	long long result = 1;
	long long currentValue = N;

	for (int i = 0; i < 32; ++i) {
		if (((P >> i) & 1) != 0) {
			result = (result * currentValue) % MOD;
		}
		currentValue = (currentValue * currentValue) % MOD;
	}

	fout << (result % MOD);

	return 0;
}