#include <fstream>
#define mod 1999999973

using namespace std;

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

int main()
{
    unsigned long long n, p;
    unsigned long long a, rez = 1;
    fin >> n >> p;
    a = n;
    for( unsigned int i = 0; (1 << i) <= p; ++i )
    {
        if( ((1 << i) & p) > 0 )
            rez = (rez * a) % mod;

        a = (a * a) % mod;
    }
    fout << rez;
    return 0;
}