#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

const int M = 1999999973;

long long a, aa, p, x, er;

int main()
{
    fin >> aa >> p;
    a = aa;
    x = er = 1;

    while(p > 0)
    {
        while(2 * x <= p)
        {
            a *= a;
            a %= M;
            x *= 2;
        }
        p -= x;
        x = 1;
        er *= a;
        er %= M;
        a = aa;
    }

    fout << er;



    return 0;
}