#include <fstream>
#define MOD 1999999973

using namespace std;

ifstream f("lgput.in");
ofstream g("lgput.out");

int n, p;

void citeste(){

    f >> p >> n;

}

void putere(){

    long long rez = 1;


    while(p){
        if (p % 2 == 1)
            rez *= n % MOD;
        n=n*n;
        p /= 2;
    }

    g << rez % MOD << "\n";;

}

int main(){

    citeste();
    putere();

    f.close();
    g.close();

    return 0;

}