#include <fstream>

constexpr long long MOD = 1999999973;

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

    long long n, p;

    fin >> n >> p;

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

    long long exp = n;
    long long 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';
}