#include <fstream>
#include <cstdint>

const uint64_t modulo = 1999999973;

int main()
{
    std::ifstream fin("lgput.in");
    std::ofstream fout("lgput.out");

    uint64_t n, p;
    fin >> n >> p;

    uint64_t res = 1;
    for (uint64_t b = n; p; p >>= 1, b = (b * b) % modulo)
    {
        if (p & 1)
            res = (res * b) % modulo;
    }

    fout << res << std::endl;

    return 0;
}