#include <iostream>
#include <fstream>

using namespace std;
long long n,d,rez=1;
long long f;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long putere()
{
   while(f)
   {
       if(f%2==1)
       {
           rez=(rez*d)%n;
           f--;
       }
       else
       {
           f/=2;
           d=(d*d)%n;
       }
   }
   return rez%n;
}

long long a;
void prim()
{
    if(a%2==0)
    {   f=f/2;
        while(a%2==0)
        {
            a/=2;
        }
    }
    for(long long i=3; i*i<=a; i+=2)
        if(a%i==0)
    {   f=(f/i)*(i-1);
        while(a%i==0) a/=i;
    }
    if(a!=1)
        f=(f/a)*(a-1);
}

int main()
{
   fin>>d>>n;
   f=n;
   a=n;
   prim();
   f--;
   fout<<putere()%n;
    return 0;
}