#include <fstream>
#include <iostream>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

long long A,N;
long long phi;
long long getphi()
{
   int sol=N;
   int CN=N;
   for(long long i=2;i*i<=N;i++)
   {
       if(CN%i==0)
       {
           sol=sol-sol/i;
           while(CN%i==0)
           {
               CN=CN/i;
           }
       }
   }
   if(CN!=1)
        sol=sol-sol/CN;
   return sol;
}

long long pow()
{
    long long i=A;
    A=1;
    for(;phi>0;)
    {
        if(phi%2==1)
        {
            A=(A*i)%N;
            phi--;
        }
        i=(i*i)%N;
        phi=phi/2;
    }
    return A;
}

int main()
{
    in>>A>>N;
    phi=getphi()-1;
    out<<pow();
}