#include <cstdio>
#define MOD 1999999973
using namespace std;
long long n,p;
long long putere(long long a , long long b)
{
    if (b<0) putere(1/n,(-1)*p)%MOD;
    else if (b==0) return 1;
    else if (b%2==0) return putere(1LL*a*a%MOD,b/2)%MOD;
    else return a*putere(1LL*a*a%MOD,(b-1)/2)%MOD;
}
int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%lld %lld",&n,&p);
    printf("%lld\n",putere(n,p));
}