#include <iostream>
#include <fstream>
using namespace std;

ifstream fi("lgput.in");
ofstream fo("lgput.out");


int main()
{
    int b,p,sol=1,c=1999999973;
    fi>>p>>b;

    for(int i=0; i<31; i++)
    {
        if(p&(1<<i))
        sol=(sol*b)%c;

        b=(b*b)%c;
    }
    fo<<sol;
    return 0;
}