#include <stdio.h>
long long a,n,q,c,i;
long long im;
long power(long long base,long p,long mod){        
     long rez=1;        
     while (p>0){        
           if ((long)(p&1)==1)rez=(rez*base)%mod;        
           base=(base*base)%mod;        
           p>>=1;        
     }
return rez;        
}   
int dc(int a, int b)     
{     
    if (!b) return a;     
    return dc(b, a % b);     
}
int main()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);
    scanf("%ld %ld",&a,&n);
    for (i=2;i<n;++i){
        q=dc(i,n);
        if(q==1)c++;
        }
    im=power(a,c,n);
    printf("%ld\n",im);
    return 0;
}