#include <iostream>

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() {
  FILE *fin, *fout ;
  fin = fopen ("inversmodular.in", "r" ) ;
  fout = fopen ("inversmodular.out", "w" ) ;
  long long n, a ;
  fscanf (fin, "%lld%lld", &a, &n) ;
  fprintf (fout, "%lld ", Putere(a, Phi(n)-1, n) ) ;
  return 0;
}