#include <iostream>

using namespace std;

#define MAX 1999999973

long long  N, P, result = 1;

long long getPow(int power){
	long long p = N;
	for(int i = 0; i < power; ++i)
		p = (p * p) % MAX;
	return p;
}

int main(){
	freopen("lgput.in",  "rt", stdin);
	freopen("lgput.out", "wt", stdout);
	cin >> N >> P;
	for(int i = 0; i < 32; ++i)
		if(P & (1 << i))
			result = (result * (getPow(i))) % MAX;	
	
	cout << result;
	
	return 0;
}