#include <stdio.h>

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

  int x, mod;
  fscanf( fin, "%d%d", &x, &mod );

  int phi = mod; {
    int cmod = mod, d = 2;
    while( d * d <= cmod ){
      if( cmod % d == 0 ){
        phi /= d;
        phi *= d - 1;

        while( cmod % d == 0 )
          cmod /= d;
      }
      d++;
    }

    if( cmod > 1 ){
      phi /= cmod;
      phi *= cmod - 1;
    }
  }

  int ret = 1, base = x, exp = phi - 1;
  while( exp ) {
    if( exp & 1 )
      ret = (ret * (long long)base) % mod;
    base = (base * (long long)base) % mod;
    exp >>= 1;
  }

  fprintf( fout, "%d\n", ret );

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