#include <stdio.h>

int fi( long long n ) {
  long long nr, p;
  int d;

  d = 2;
  nr = 1;
  while ( d * d <= n ) {
    p = 1;
    while ( n % d == 0 ) {
      n /= d;
      p *= d;
    }
    if ( p > 1 ) {
      nr = nr * (d - 1) * (p / d);
    }
    ++d;
  }
  if ( n > 1 ) {
    nr = n - 1;
  }
  return nr;
}

int main() {
  FILE *fin = fopen( "inversmodular.in", "r" );
  FILE *fout = fopen( "inversmodular.out", "w" );
  int n, mod, e;
  long long a, p = 1;

  fscanf( fin, "%lld%d", &a, &n );
  mod = n;
  e = fi( n ) - 1;
  while ( e > 0 ) {
    if ( e % 2 == 1 ) {
      p = (p * a) % mod;
    }
    a = (a * a) % mod;
    e /= 2;
  }
  fprintf( fout, "%lld", p );
  fclose( fin );
  fclose( fout );
  return 0;
}