#include <fstream>
#define MOD 1999999973

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

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

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

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