#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int main()
{
   int N,A,f,i,r,n;
   long long p;
   fin>>A;
   fin>>N;
   n=N;
   f=0;
   p=1;
   i=2;
   f=N;
   while(i*i<=N)
   {
       if(N%i==0)
       {
           f=f/i*(i-1);
           while(N%i==0);
           {
               N=N/i;
           }
       }
       i++;
   }
   if(N!=1) f=f/N*(N-1);

   f=f-1;
   while(f!=0)
    {
        if(f%2!=0)
        {
            p=(p*A)%n;
        }
        A=(A*A)%n;
        f=f/2;
    }

    fout<<p;
   return 0;
}