#include <bits/stdc++.h>
#define mod 1999999973
using namespace std;

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

long long n, p, r=1;

int main () {
    in >> n >> p;
    if (p == 0)
    {
        out << 1;
        in.close();
        out.close();
        return 0;
    }
    while (p)
    {
        if (p % 2 != 0) // Daca o
        {
            r = (r*n) % mod;
        }
        // cazul de baza  SE RRDICA. MEREU la patreat
        n = (n*n)%mod;
        p=p/2;
    }
    out << r;

    in.close();
    out.close();
    return 0;
}