/* Ridicare la putere folosind exponentiere logaritmica */
#include <fstream>
using namespace std;
#define MOD 1999999973

long long N, P, R;

void Pow(long long P)
{
    if (P == 0)
    {
        R = 1;
        return;
    }
    else
    {
        Pow(P / 2);
        if (P % 2)
        {
            R = (R * R * N) % MOD;
        }
        else
        {
            R = (R * R) % MOD;
        }
    }
}

int main()
{
    ifstream f("lgput.in");
    ofstream g("lgput.out");
    f >> N >> P;
    Pow(P);
    g << R;
}