#include <cstdio>
#define M 1999999973

using namespace std;

long long numar, putere, rezultat;

int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%lld %lld",&numar,&putere);
    rezultat=1;
    for(int i=0;(1 << i)<=putere;i++){
        if(((1<<i)&putere)!=0)
            rezultat=(rezultat*numar)%M;
        numar=(numar*numar)%M;
    }
    printf("%lld\n", rezultat);
    return 0;
}