#include <iostream>
#include <cstdio>


using namespace std;

#define MAX 1999999973

long long  N, P, result = 1;

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