#include<fstream>
using namespace std;
int a,n;
int Phi(int n)
{
   int d,fi;
   d=2;
   fi=n;
   while(n>1 && d*d<=n)
   {
            if(n%d==0)
            {
                fi=(fi/d)*(d-1);
                while(n%d==0)
                n=n/d;
            }
       d++;
   }
   if(n>1)fi=(fi/n)*(n-1);
    return fi;

}
int Putere(int a,int p)
{
    int prod;
    prod=1;
    while(p>0)
    {
        if(p%2==1)
        {
            p--;
            prod=1LL*prod*a%n;
        }
        p=p/2;
        a=(1LL*a*a)%n;
    }
    return prod;
}

    int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int p;
    fin>>a>>n;
    p=Phi(n)-1;
    fout<<Putere(a,p)<<"\n";
    fin.close();
    fout.close();
}