#include <iostream>
#include<fstream>
using namespace std;
int a,n;
int Fi(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 k)
{
    int prod;
    prod=1;
    while(k>0)
    {
        if(k%2==1)
        {
            k--;
            prod=1LL*prod*a%n;
        }
        k=k/2;
        a=(1LL*a*a)%n;
    }
    return prod;
}

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