#include<stdio.h>

#define plm long long

plm A,N,phi,sol;

int getphi(int nr)
{
    int cur=nr;
    
    for(int i=2;i*i<=nr;++i)
        if (nr % i == 0)
            {
            while (nr % i==0) nr/=i;
            cur=(cur/i)*(i-1);
            }
    if (nr!=1)
        cur=(cur/nr)*(nr-1);
        
    return cur;
            
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&A,&N);
    phi=getphi(N)-1;
    
    plm r,b;
    for( r=A , sol=1 ; phi ; phi/=2)
        {
        if (phi%2==1)
            sol = (sol * r) % N;
            
        r= (r * r) % N;
        }
        
    printf("%lld\n",sol);
    return 0;
}