/*
 * lgput.cpp
 *
 *  Created on: Jun 8, 2009
 *      Author: stefan
 */

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);
	unsigned long long int N, P, rezultat = 1;

	cin >> N >> P;
	while(P)
	{
		if(P & 1)
			rezultat = (rezultat * N) % 1999999973;
		P >>= 1;
		N = (N*N) % 1999999973;
	}
	cout << rezultat;

	return 0;
}