#include <iostream>
#include <fstream>

const int mod = 1999999973;

long long int fast_exp(int n, int p)
{
    if (p == 0)
        return 1 % mod;

    if (p == 1)
        return n % mod;

    long long result = (n * n) % mod;
    p--;

    while (p--)
    {
        result = (result * result) % mod;
    }

    return result;
}

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

    int n, p;

    in >> n;
    in >> p;

    int counter = 0;
    long long result = 1;

    while ((p >> 1) != 0)
    {
        if ((p >> 1) & 1 == 1)
        {
            result *= fast_exp(n, counter);
        }
        counter++;

        p >>= 1;
    }

    result %= mod;

    out << result << std::endl;

    in.close();
    out.close();

    return 0;
}