#include <cstdio>
#define M 1999999973

using namespace std;

long long inmultire (long long X , long long Y) {
    if (Y == 0)
        return 0;
    if (Y == 1)
        return X % M;
    return (2 * inmultire (X , Y / 2) % M + inmultire (X , Y % 2) % M) % M;
}

int main () {
    long long B , P , m;

    freopen ("lgput.in" , "r" , stdin);
    freopen ("lgput.out" , "w" , stdout);

    while (scanf ("%lld%lld" , &B , &P) != EOF) {
        for (m = 1 ; P ; P >>= 1) {
            if (P & 1)
                m = inmultire (m , B);
            B = inmultire (B , B);
        }
        printf ("%lld\n" , m);
    }
    return 0;
}