#include<stdio.h>
#define ll long long
#define MOD 1999999973
int n,p;
int log(int exp)
{
    if(!exp)
        return 1;
    int r=log(exp/2);
    if(exp%2==0)
        return ((ll)r*r)%MOD;
    return ((((ll)r*r)%MOD)*(ll)n)%MOD;
}
int main ()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%d%d",&n,&p);
    n%=MOD;
    int r=log(p);
    printf("%d\n",r);
    return 0;
}