#include <cstdio>
#define MOD 1999999973
using namespace std;

long long n, p;
int main(){
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    scanf("%lld%lld", &n, &p);
    long long Sol = 1, aux = n;
    for(long long i = 0; (long long)((long long)1 << i) <= p ; ++i){
        if((p & ((long long)((long long)1 << i))) > 0) Sol = (Sol * aux) % MOD;
        aux = (aux * aux) % MOD;
    }
    printf("%lld", Sol);
    return 0;

}