#include <fstream>
using namespace std;

long long Phi (long long n ) {
  long long val, p ;
	p = 2 ;
  val = n ;
  while (n > 0 && p * p <= n ) {
    if (n % p == 0 ) {
      val = val * ( p - 1 ) / p ;
      while (n % p == 0 )
        n /= p ;
    }
    p++;
  }
  if (n > 1 )
    val = val * ( n - 1 ) / n ; /// a mai ramas un nr. prim
  return val ;
}


long long Putere (long long a, long long n, long long mod ) { /// a ^ n
  long long prod ;
  prod = 1 ;
  while (n > 0 ) {
    if (n % 2 == 1 ) {
      prod = ( (prod % mod) * (a % mod) ) % mod ;
      n--;
    } else {
      a = (a % mod) * (a % mod) % mod ;
      n /= 2 ;
    }
  }
  return prod ;
}



int main() {

  ifstream fin ("inversmodular.in") ;
  ofstream fout("inversmodular.out") ;
  long long n, a ;
  fin>>a>>n;
  fout<<Putere(a, Phi(n)-1, n)  ;
  return 0;

}