#include <fstream>
using namespace std;
long long Phi( long long n ){
  long long d, p, phi, f;
  phi = 1;
  for( d = 2; d * d <= n; d++ ){
    p = 0;
    f = 1;
    while( n % d == 0 ){
      p++;
      f*=d;
      n/=d;
    }
    if( p > 0){
      phi *= ( f / d ) * ( d - 1 );
    }
  }
  if( n > 1 ){
    phi*= ( n - 1 );
  }
  return phi;
}
int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    long long a, n, p;
    in >> a >> n;
    long long exp = Phi(n) - 1;
    p = 1;
    while ( exp > 0 ) {
      if(exp % 2 == 1)
        p = (p * a) % n;
      a = (a * a) % n;
      exp /= 2;
    }
    out << p;
    return 0;

}