#include <fstream>
#define MOD 1999999973

using namespace std;
FILE * fin = fopen("lgput.in", "r");
FILE * fout = fopen("lgput.out", "w");

long long int putere(long long int, long long int);

int main()
{
    long long int nr, p;
    
    fscanf(fin, "%lld %lld", &nr, &p);
    fprintf(fout, "%lld\n", putere(nr, p));
    
    fclose(fin);
    fclose(fout);
    return 0;
}

long long int putere(long long int x, long long int p)
{
    if (p==0) return 1;
    if (p==1) return x%MOD;
    
    if (p%2==0) return (long long int) ( putere(x, p/2)*putere(x, p/2) ) % MOD;
    return (long long int) ( putere(x, p/2)*putere(x, p/2)*x ) % MOD;
}