#include<fstream>
using namespace std;
int main()
{
    ifstream read("lgput.in");
    ofstream write("lgput.out");
    unsigned long long int n;
    unsigned long long int p;
    read>>n>>p;
    unsigned long long int lgput = 1;
    unsigned long long int cur_power=1;
    unsigned long long int h = (n % 1999999973);
    while(p != 0)
    {
        while(cur_power * 2 <= p)
        {
            lgput = (lgput * h) % 1999999973;
            cur_power = cur_power * 2;
            h = ( h * h ) % 1999999973;
        }
        p = p - cur_power;
        cur_power = 1;
        h = n;
    }
    write<<lgput;
    return 0;
}