#include<fstream.h>

#define rest 1999999973

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

long long res, n, p;

int main()
{
    f>>n>>p;
    res=1;
    while(n){
        if( n%2==0 ){
            res=(res*p)%rest;
            n--;
        }
            else{
                p=(p*p)%rest;
                n=n/2;
            }
    }

    g<<res<<'\n';
    g.close();
    return 0;
}