#include <fstream>

using namespace std;

int phi ( int n ) {
  int cpy_n, d, phi;

  cpy_n = n;
  phi = 1;
  d = 2;

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

}

int main()
{
    int a, modul, pow, invers_a;
    ifstream cin ( "inversmodular.in" );
    ofstream cout ( "inversmodular.out" );

    cin >> a >> modul;
    pow = phi( modul ) - 1;

    invers_a = 1;
    while ( pow > 0 ) {
      if ( pow % 2 == 1 )
        invers_a = (long long) invers_a * a % modul;
      a = (long long) a * a % modul;
      pow /= 2;
    }

    cout << invers_a << "\n";

    return 0;
}