#include <iostream>

using namespace std;
int n,d,rez=1;
int f;
int putere()
{
   while(f)
   {
       if(f%2==1)
       {
           rez=(rez*d)%n;
           f--;
       }
       else
       {
           f/=2;
           d=(d*d)%n;
       }

   }
   return rez%n;

}

int a;
void prim()
{
    if(a%2==0)
    {   f=f/2;
        while(a%2==0)
        {
            a/=2;
        }
    }
    for(int 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()
{

   cin>>d>>n;
   f=n;
   a=n;
   prim();
   f--;
   cout<<putere()%n;

    return 0;
}