#include <fstream>
#include <iostream>

using namespace std;

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

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

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

        p = 1ll*p*p;
        n /= 2;
    }

    fout<<result;
    return 0;
}