#include <bits/stdc++.h>
using namespace std;
#define l64 long long 
l64 n,a;

l64 get_phi(l64 n)
{
 int i=2;
 double phi=n;
 for (i=2;n>1;++i)
   {
   	int power=0;
	 while(n%i==0) 
	    {
		n/=i;
		++power;
	    }
    if (power) phi*=1.00*(i-1)/i;
   }
 return phi;
}

l64 power(l64 baza, l64 exp)
{
 l64 aux=1;
 while(exp)
  {
   if (exp%2==0)
        {
         baza=(baza*baza)%n;
         exp/=2;
        }
   if (exp%2==1)
        {
         aux=(aux*baza)%n;
         --exp;
		} 	
  }
 return aux;
}

int main(void)
{
 ifstream  cin("inversmodular.in");
 ofstream cout("inversmodular.out");
 cin>>a>>n;
 cout<<1LL*power(a,get_phi(n)-1);
 return 0;
}