#include <stdio.h>
#define ll long long
ll n,m,p,sol;
ll euler (ll m)
{
    ll i,nrc=m;
    for (i=2; i*i<=nrc; ++i)
        if (!(nrc%i))
        {
            while (!(nrc%i))
                m/=i;
            nrc=(nrc/i)*(i-1);
        }
    if (nrc!=1)
        nrc=(nrc/m)*(m-1);
    return nrc;
}
ll lgput (ll n,ll p,ll 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 ("%lld%lld",&n,&m);
    p=euler (m)-1;
    printf ("%lld",lgput (n,p,m));
    return 0;
}