#include <fstream> 
using namespace std; 

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

const int MOD = 1999999973; 

int N, P, aux, v[101], k, R = 1; 

int main () { 
	fin >> N >> P;  
	while(P) { 
		v[++k] = P % 2; 
		P /= 2; 
	}

	for(int i = k; i >= 1; i--) { 
		aux = R; 
		if(v[i] == 1) 
 			R = (1LL * R * N) % MOD; 

 		R = (1LL * R * aux) % MOD; 
	}	 

	fout << R << '\n'; 
	fin.close (); 
	fout.close (); 
	return 0; 
}