#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;

    for(int i=0; i<p; i++){
        if (i && (1<<p))
            rez = rez * n % MOD;
        n = n * n;
    }

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

}

int main(){

    citeste();
    putere();

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

    return 0;

}