#include <iostream>

using namespace std;

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

int Phi (int n ) {
  int val, p ;
  p = 2 ;
  val = n ;
  while (n > 0 && p <= n ) {
    while (n % p == 0 ) {
      val = val * ( p - 1 ) / p ;
      n /= p ;
    }
    p++;
  }
  return val ;
}

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;
}