#include <iostream>
#include <fstream>
#define MOD 1999999973

using namespace std;

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

int main()
{
    long long int n, p;
    in >> n >> p;
    in.close();
    long long int aux = n;
    long long int res = 1;
    for (long long int i = 0; (1<<i) <= p; i++)
    {
        if (p & (1<<i))
            res = (res * aux) % MOD;
        aux = (aux * aux) % MOD;
    }
    out << res % MOD << "\n";
    out.close();
    return 0;
}