#include <fstream>

using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
const int MOD=1999999973;
int n,a;

int main()
{
    f>>n>>a;
    int p=1;
    while(n){
        int b=n&1;
        if(b)
            p=(long long)p*a%MOD;
        a=a*a%MOD;
        n/=2;
    }
    g<<p;
    return 0;
}