#include<cstdio>
int n;
long long ridic(long long x, long long put)
    {if(put==0)
        return 1;
    else
        if(put%2==1)
            {put--;
            return (x*ridic(x,put))%n;
            }
        else
            {put/=2;
            x=(x*x)%n;
            return ridic(x,put)%n;
            }
    }
int main ()
{freopen ("inversmodular.in","r",stdin);
freopen ("inversmodular.out","w",stdout);
int a,i,cn;
long long x,phi;
scanf("%d%d",&a,&n);
phi=n;
cn=n;
for(i=2;i*i<=n;i++)
    if(n%i==0)
        {phi/=i;
        phi*=i-1;
        while(n%i==0)
            n/=i;
        }
if(n!=1)
    {phi/=n;
    phi*=(n-1);
    }
n=cn;
a=a%n;
x=ridic(a,phi-1);
printf("%lld",x);
return 0;
}