#include <iostream>
#include <cmath>
#include <fstream>

long long int pow_log(int x, int n)
{
    if (n == 1)
        return x;

    if (n == 0)
        return 1;

    if (n % 2 == 0)
        return pow_log(x * x, n / 2);
    return x * pow_log(x * x, (n - 1) / 2);
}

int main()
{
    int number, power;

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

    in >> number;
    in >> power;

    out << 1999999973 % pow_log(number, power)  << std::endl;

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

    return 0;
}