#include <fstream>
#include <iostream>

using namespace std;

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

int main()
{
    const unsigned long long MOD = 1999999973;
    unsigned long long n, p, result = 1;
    fin>>n>>p;

    while (n) {
        if (n%2) result = (1ll*result*p)%MOD;

        p = (1ll*p*p)%MOD;
        n /= 2;
    }

    fout<<result%MOD;
    return 0;
}