#include <cstdio>

using namespace std;

int MOD,A;

int phi (int a)
{
    int i,res=a;
    for (i=2; i*i<=a; i++)
    {
        if (a%i==0)
        {
            while (a%i==0)
            {
                a/=i;
            }
            res/=i;
            res*=(i-1);
        }
    }
    if (a!=1)
    {
        res/=a;
        res*=(a-1);
    }
    return res;
}

long long explog (long long b,int e)
{
    long long rez=1;
    while (e!=0)
    {
        if (e%2==1)
        {
            rez=(rez*b)%MOD;
            e--;
        }
        else
        {
            b=(b*b)%MOD;
            e/=2;
        }
    }
    return rez;
}

int main()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);

    scanf ("%d %d",&A,&MOD);

    printf ("%lld\n",explog(A,phi(MOD)-1));

    return 0;
}