#include <stdio.h>
int n,m,p,sol;
int euler (int m)
{
    int i,nrc=m;
    for (i=2; i*i<=m; ++i)
        if (!(m%i))
        {
            while (!(m%i))
                m/=i;
            nrc=(nrc/i)*(i-1);
        }
    if (m!=1)
        nrc=(nrc/m)*(m-1);
    return nrc;    
}
int lgput (int n,int p,int MOD)
{
    for (sol=1; p; p>>=1)
    {
        if (p&1)
            sol=(sol*n)%MOD;
        n=(n*n)%MOD;
    }
    return sol;
}
int main ()
{
	freopen ("inversmodular.in","r",stdin);
	freopen ("inversmodular.out","w",stdout);
    scanf ("%d%d",&n,&m);
    p=euler (m)-1;
    printf ("%d",lgput (n,p,m));
    return 0;
}