#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 rez = 1ll;

    for (int i = 0; (1ll << i) <= p; i++)
    {
        if (p & (1ll << i))
            rez = (rez * n) % MOD;
        n = (n * n) % MOD;
    }

    out << rez << "\n";

    out.close();
    return 0;
}