#include <fstream>

using namespace std;

long long phi ( long long n ) {
  long long d = 2, phi = 1;
  while ( d * d <= n && n % d != 0 )
    d ++;
  if ( d * d > n )
    return n - 1;
  d = 2;
  while ( n > 1 ) {
    int cnt = 0;
    while ( n % d == 0 ) {
      if ( cnt == 0 )
        phi = phi * (d - 1);
      else
        phi = phi * d;
      n = n / d;
    }
    d++;
  }
  return phi;
}

int main()
{
    long long x, mod, pow;
    long long inv = 1;
    ifstream fin ( "inversmodular.in" );
    ofstream fout ( "inversmodular.out" );

    fin >> x >> mod;
    pow = phi ( mod ) - 1;
    while ( pow > 0 ) {
      if ( pow % 2 == 1 )
        inv = (inv * x ) % mod;
      x = (x * x) % mod;
      pow /= 2;
    }
    fout << inv;

    fin.close();
    fout.close();

    return 0;
}