#include <cstdio>

using namespace std;

void euclidExtended(long long A, long long B, long long &X, long long &Y)
{ // A * X + B * Y = GCD(A,B)
  if (B == 0) {
    X = 1;
    Y = 0;
    return;
  }
  long long X_, Y_;
  euclidExtended(B, A % B, X_, Y_);
  // B * X_  + (A - [A/B] * B) * Y_ = GCD(A, B)
  X = Y_;
  Y = X_ - (A/B) * Y_;
}


int main()
{
  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);

  long long a, mod;
  scanf("%lld%lld", &a, &mod);
  // Precondition: gcd(a, mod) is 1 otherwise a^-1 (mod m) doesn't exist
  // a * X + mod * Y = gcd(a, mod) <=>
  // a * X + mod * Y = 1 <=>
  // a * X = 1 (mod mod) so X is a^-1
  long long x, y;
  euclidExtended(a, mod, x, y);
  printf("%lld\n", (x % mod + mod)%mod);
  
  return 0;
}