#include <fstream>

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

int main()
{
    long long n, en , rez, p, k = 1, pow = 1;
    const long long m = 1999999973;

    fin >> en >> p; rez = en % m; n = en % m;

    while(pow < p)
    {
        if(pow + k <= p)
        {
            rez = (rez * n) % m;
            pow = pow + k;
            k = k * 2; n = (n * n)%m;
        }
        else k = 1, n = en % m;
    }

    fout << rez;

    return 0;
}