#pragma GCC optimize("O2")

#include <fstream>

using namespace std;

ifstream fin("lgput.in");
ofstream fout("lgput.out");

bool isEven(long long int val) {
    if(val % 2 == 0) {
        return true;
    }
    return false;
}

long long int exp_by_squaring(int base, int exponent) {
    if(exponent < 0) {
        return exp_by_squaring(1 / base, -exponent);
    } else if(exponent == 0) {
        return 1;
    } else if(isEven(exponent)) {
        return exp_by_squaring(base * base, exponent / 2);
    } else if(!isEven(exponent)) {
        return base * exp_by_squaring(base * base, (exponent - 1) / 2);
    }
    return 0;
}

int main()
{
    long long int base, exponent;
    fin >> base >> exponent;
    fout << exp_by_squaring(base, exponent) % 1999999973 << endl;
    return 0;
}