#include <iostream>

using namespace std;

int Phi (int n ) {
  int 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 ;
}

int Putere (int a, int n, int mod ) { /// a ^ n
  int 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" ) ;
  int n, a ;
  fscanf (fin, "%d%d", &a, &n) ;
  fprintf (fout, "%d ", Putere(a, Phi(n)-1, n) ) ;
  return 0;
}