#include <iostream>
#include <fstream>
using namespace std;
#include <vector>

vector<int> reverse_number_on_bites(int number){
	 vector<int> vec;
	 vec.resize(1000);
	 for (int i = 0; i < vec.size(); i++){
	 	vec[i] = 0;
	 }
	 int nr = -1;
	 while(number != 0){
		if(number % 2 == 0){
			vec[vec.size() -1 - (++nr)] = 0;
			
		}else {
			vec[vec.size() -1 - (++nr)] = 1;
			
		}
		number=number/2;
	}
	return vec;
}


int ridicare(int a, int b){
	long int r = 1999999973;
	int rezultat;
	std::vector<int> inter = reverse_number_on_bites(b);
	int m = 1;
	for(int i = 0; i < inter.size(); i++){
		m = m * m;
		if(inter[i] == 1){
			m = m * a;
		}
	}
	return m%r;

}

int main(){
	std::ifstream fin("lgput.in");
	std::ofstream fout("lgput.out");
	int rez, a, b;
	fin >> a >> b;
    
	rez = ridicare(a, b);
	fout << rez <<'\n';
	
	 
	return 0;

}