#include <stdio.h>

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

  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 a, n, p = 1, mod, e;

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