#include <fstream>

using  namespace std;

ifstream cin("lgput.in");
ofstream cout("lgput.out");

long long int ridicare_log_mod(long long int nr, int power,long long int mod){
	nr = nr % mod;
	if(power>0){
		cout << nr << " " << power << "\n";
		if(!power%2)
			return ridicare_log_mod(nr*nr, power/2, mod)%mod;
		else 
			return (nr%mod*ridicare_log_mod(nr, power-1, mod))%mod;		
	}
	else 
		return 1;
}
int main(int argc, char *argv[]){
	long long int n, p,m = 1999999973;
	cin >> n >> p;
	cout << ridicare_log_mod(n,p,m);
}