//#1010
#include <iostream>
#include <fstream>
#include <fstream>
#include <vector>

using namespace std;

/*2*2*2*2*....*2
2*2 = 4 (2^2)
2^2 * 2^2 = 16 (2^4)
2^4*2^4 = 256  (2^8)

2^8 * 2^8 > 2^10 => 2^10 / 2^8 = 2^2 => raspunsul = 2^8 * 2^2

// noi vrem sa gasim exponentul cel mai mare care putem sa il ,,scadem,, si dupa urmatorii exponenti pana cand p devine 0

int main(){
    ifstream fin("lgput.in");
    ofstream fout("lgput.out");
    int n, p;
    fin>>n>>p;
    unsigned long long pow[33], exp[33];
    //1,2,4,8,16,32,64 ....
    pow[1]=n;
    exp[1]=1;
    for(int i=2; i<=32; i++)
    {
    	pow[i]= (pow[i-1] * pow[i-1]) % 1999999973;
    	exp[i] = exp[i-1] * 2;
    }

    //5 ^ 100000

    int i=32;
    long long rez=1;
    while (p){
    	if(exp[i] <= p){
        	p-=exp[i];
            rez = (rez*pow[i])  % 1999999973;

        }else i--;

    }

    fout<<rez;

}
*/
int main(){
  ifstream fin("lgput.in");
  	ofstream fout("lgput.out");
    int n, p;
    fin>>n>>p;
  	unsigned long long rez=1, pown=n;
  	for (int i=0; i<=31 && p; ++i){ //luam bitul de pe pozitia i de la dr la st
    	if((1<<i) & p)
          	rez = (rez*pown) % 1999999973;
      	pown=(pown*pown) % 1999999973;
    }
  	fout<<rez;
}