#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;

    long long exp = n;
    long long sol = 1;

    while (p > 0)
    {
        bool bit = p & 1;
        if (bit)
        {
            sol *= exp;
            sol %= MOD;
        }
        exp *= exp;
        exp %= MOD;
        p >>= 1;
    }

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