#include <cstdio>

#define MOD 1999999973

long long n, p, ans;

int main() {
    freopen("lgput.in", "r", stdin);
    // freopen("lgput.out", "w", stdout);

    scanf("%lld%lld", &n, &p);
    
    ans = n;
    while (1 < p) {
        ans = (ans * ans) % MOD;
        if (1 == p % 2) ans = (ans * n) % MOD;
        p /= 2;
    }

    printf("%lld\n", ans);

    return 0;
}