#include<fstream>
using namespace std;
int main()
{
        long long i, n, a,p,nr;
        ifstream f("inversmodular.in");
        f>>a>>n;
        f.close();
        p=n;
        nr=n;
        for(i=2;i*i<=n;i++)
        {
                if(n%i==0){
                  while(n%i==0)  n/=i;
                  p/=i;p*=(i-1);
                }
        }
        if( n!=1 )  p=((p/n)*(n-1));
        i=1;--p;
        while(p)
        {
                if( (p&1) )
                {
                        i*=a;
                        i=i%nr;
                }
                a*=a;
                a=a%nr;
                p>>=1;
        }
        ofstream g("inversmodular.out");
        g<<i<<'\n';
        g.close();
        return 0;
}