#include <fstream>

#define MOD 1999999973

using namespace std;

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

long long n, p, current, ans, pow_sum;

void read() {
    cin >> n >> p;
}

long long lgput(long long n, long long p) {
    current = n;
    ans = 1;
    for(int i = 0; i < 32 and pow_sum < p; ++i) {
        if( (1 << i) & p) {
            pow_sum += (1 << i);
            ans *= current;
            ans %= MOD;
        }
        current *= current % MOD;
    }
    return ans;
}

int main() {
    read();
    cout << lgput(n, p) << '\n';
    return 0;
}