#include <fstream>
#define MODULO 1999999973

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


long long n, p;

int exp(int  x, int n){

    if(n==0)return 1;
    if(n==1)return x%MODULO;
    if(n%2==0)return exp(x*x, n/2)%MODULO;
    if(n%2==1)return (x * exp(x*x, (n-1)/2))%MODULO; 

    return -1;
}

int main(){

    //ridicare in timp logaritmic
    fin>>n>>p;
    fout<<exp(n,p)%MODULO;


    return 0;
}