#include <cstdio>

using namespace std;

#define FILEIN "lgput.in"
#define FILEOUT "lgput.out"
#define MOD 1999999973

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    unsigned long long int N, P, F, P0;
    scanf("%llu %llu", &N, &P0);

    F = 1; P = N;

    for ( int p = 0; (1 << p) <= P0; p++ ) {
        if ((1 << p) & P0) {
            F *= P;
            F %= MOD;
        }
        P *= P;
        P %= MOD;
    }

    printf("%llu\n", F);


    return 0;
}