#include <stdio.h>
#define MOD 1999999973
using namespace std;

long long N, P, SOL = 1, i;

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

    scanf("%d%d", &N, &P);

    for(i = 0; (1 << i) <= P; i++){
            if( ((1 << i) & P) > 0){
                SOL = (SOL * N) % MOD;
            }
            N = (N * N) % MOD;
    }
    printf("%d ", SOL);
}