#include <fstream>
#include <iostream>

using namespace std;

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

long long putere (long long a, long long b)
{
    if (b == 1)
    {
        return a;
    }
    if (b % 2 == 0)
    {
        long long n = b / 2;
        return putere(a * a, n);
    }
    else
    {
        return putere (a, (b - 1) / 2) * a;
    }
}

int main()
{

    // (a^b) % c = ?
    // 1 <= a <= 2 * 10^9
    // 1 <= b <= 2 * 10^19
    // 2 <= c <= 666013

    long long a, b, c = 1999999973;
    fin >> a >> b;
    long long d = putere(a, b);
    fout << d % c;

    return 0;
}