#include <stdio.h>

int mod;

int phi( int n ){
  int d = 2, rez = n;

  while( d * d <= n ){
    if( n % d == 0 ){
      rez /= d;
      rez *= (d - 1);

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

  if( n != 1 ){
    rez /= n;
    rez *= (n - 1);
  }

  return rez;
}

int lgput( int base, int exp ){
  int rez = 1;

  while( exp ){
    if( exp & 1 )
      rez = ((long long)rez * base) % mod;

    base = ((long long)base * base) % mod;
    exp >>= 1;
  }

  return rez;
}

FILE *fin, *fout;

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

  fscanf( fin, "%d%d", &a, &mod );

  exp = phi( mod ) - 1;

  if( !mod )
    return 2;
  
  fprintf( fout, "%d\n", lgput( a, exp ) );

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