#include <fstream>
using namespace std;

ifstream is("monkey.in");
ofstream os("monkey.out");

#define D 1999999973
long long int n, p;
int LG( int n, int p );

int main()
{
    is >> n >> p;

    os << LG( n, p );

    is.close();
    os.close();
    return 0;
}

int LG( int n, int p )
{
    if ( n == 0 )
        return 1;
    int aux = LG( n / 2, p );
    aux = ( aux * aux ) % D;
    if ( n & 1 )
    {
        aux *= p;
        aux %= D;
    }
    return aux;
}