#include <fstream>

using namespace std;
int c ;
int euler ( int n )
{

    int d = 2 , phi = n , e = 0 ;
    while( d * d <= n && n > 1 )
    {
        while( n % d == 0 )
        {
            e++ ;
            n /= d ;
        }
        if( e > 0 )
          phi = phi / d * ( d - 1 ) ;
          e = 0 ;
          d ++ ;
    }
    if( n > 1 )
    phi = phi / n * ( n - 1 ) ;
    return phi ;
}
int mod ( int a , int b) {
  if ( b == 0 )
    return 1;
  else {
    long long x = mod (a, b / 2);
    if ( b % 2 == 0)
      return x * x % c;
    else
      return x * x % c * a % c;
  }
}
ifstream cin ("inversmodular.in") ;
ofstream cout ("inversmodular.out") ;
int main()
{

    int a , phi ;
    cin >> a >> c ;
    phi = euler ( c ) - 1 ;
    cout << mod ( a , phi ) ;
    return 0;
}