#include <iostream>
#include <fstream>

#define MODUL 1999999973

using namespace std;

int main()
{
    ifstream fin("lgput.in");
    ofstream fout("lgput.out");
    long long n, p, rez, q, cnt;
    fin >> n >> p;

    n %= MODUL;
    rez = 1;
    while (p > 1) {
        q = n*n%MODUL;
        cnt = 4;
        while (cnt <= p) {
            q = q*q%MODUL;
            cnt *= 2;
        }
        rez = rez*q%MODUL;
        //cout << cnt/2 << ' ' << p << ' ' << q;
        p -= cnt/2;
    }
    if (p == 1)
        rez = rez*n%MODUL;

    fout << rez;

    return 0;
}