#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;
}

int main(){
  int a, exp;

  scanf( "%d%d", &a, &mod );

  exp = phi( mod ) - 1;

  printf( "%d\n", lgput( a, exp ) );
}