#include <fstream>
#include <iostream>
using namespace std;
long long n, p;

long long exp(long long x, long long n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    if (n % 2 == 0)
        return (exp((x * x) % 1999999973, n / 2) % 1999999973);
    if (n % 2 != 0)
        return ((x * (exp(x * x, (n - 1) / 2) % 1999999973)) % 1999999973);
}

int main()
{
    ifstream cin("lgput.in");
    ofstream cout("lgput.out");
    cin >> n >> p;
    cout << exp(n, p);
    return 0;
}