#include <iostream>
#include <fstream>

#define MOD 1999999973

using namespace std;

long long N, P;

long long Putere (long long N, long long P)
{
    long long S, i, n;
    S=N;
    while (P>1)
    {
        if (P%2==0)
        {
            S*=S;
            S%=MOD;
            P/=2;
        }
        else
        {
            S*=N;
            S%=MOD;
            P--;
        }
    }
    return S;
}

int main()
{
    ifstream fin ("lgput.in");
    ofstream fout ("lgput.out");
    fin >> N >> P;
    fout << Putere (N, P) << " ";
    fin.close ();
    fout.close ();
    return 0;
}