#include <fstream>

constexpr int MOD = 1999999973;

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

    int n, p;

    fin >> n >> p;

    constexpr std::size_t BITS = sizeof(p) * 8;

    int exp = n;
    int sol = 1;

    for (std::size_t i = 0; i < BITS; ++i)
    {
        bool bit = (p >> i) & 1;
        if (bit)
        {
            sol *= exp;
            sol %= MOD;
        }
        exp *= exp;
        exp %= MOD;
    }

    fout << sol << '\n';
}