#include<bits/stdc++.h>
#define MOD 1999999973

using namespace std;

int lgput(uint32_t n, uint32_t p){ //n la p
    //cout << "n:" << n << "\n";
    //cout << "p:" << p << "\n";
    if (p == 0) return 1;
    //else if (p == 1) return n;
    else if (p < 0) return lgput(1 / n, -p);
    else if (p & 1) return n * lgput(n * n, (p - 1) / 2);
    else return lgput(n * n, p / 2);
}

int main(){
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    uint32_t n, p;
    cin >> n >> p;
    cout << lgput(n, p) % MOD;
    return 0;
}