#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int i,n,x,y,a,b,c,d;
long long putere(long long x, int n)
{
    long long p=1;
    while(n)
    {

            if(n&1)
        {   p=p*x;
            n--;
        }
        x=x*x;
        n=n/2;}
        return p;
}
int fi(int n)
{
    int d=2;
    int m=n;
    if(n%d==0)
    {
        m=m/d;
        m=m*(d-1);
        while(n%d==0)
            n=n/d;
    }
    for(d=3;d*d<=n;d=d+2)
    {
        if(n%d==0)
        {
            m=m/d;
            m=m*(d-1);
            while(n%d==0)
                n=n/d;
        }
    }
    if(n!=1)
        {m=m/n;
         m=m*(n-1);
        }
    return m;
}
int main()
{
    f>>a>>b;
    i=fi(b);
    x=putere(a,i-1);
    g<<x%b;;
    return 0;
}