#include <stdio.h>
#include <ctype.h>

// Program de Mircea Rebengiuc
// inceput pe 2021.04.21

FILE *fin, *fout;

int mod;

static inline int getPhi( int n ){
  int d = 2, phi = n;
    
  while( d * d <= n ){
    if( n % d == 0 ){// daca am gasit un nou factor prim
      phi /= d;
      phi *= (d - 1);
      
      while( n % d == 0 )
        n /= d;
    }
    
    d++;
  }
  
  if( n > 1 ){
    phi /= n;
    phi *= (n - 1);
  }
  
  return phi;
}

static inline int fastexp( int a, int n ){
  int acc = 1;

  while( n > 0 ){
    if( n & 1 )
      acc = (((long long)acc) * a) % mod;
    a = (((long long)a) * a) % mod;
    n /= 2;
  }

  return acc;
}

int main(){
  fin  = fopen("inversmodular.in",  "r");
  fout = fopen("inversmodular.out", "w");

  int a;

  fscanf(fin, "%d%d", &a, &mod);
  fprintf(fout, "%d\n", fastexp(a, getPhi(mod) - 1));

  fclose(fin);
  fclose(fout);
  return 0;
}