#include <cstdint>
#include <fstream>

std::ifstream  cin("inversmodular.in");
std::ofstream cout("inversmodular.out");

int64_t A, N, nr, a, b, c;
int64_t euclid(int64_t x0, int64_t x1, int64_t& alpha0, int64_t& beta1) {

  if (x1 == 0) {
    alpha0 = 1;
    beta1 = 0;
    return x0;
  }

  int64_t c1, x2, cmmdc;
  c1 = x0 / x1;
  x2 =  x0 % x1;
  int64_t alpha1, beta2;
  
  cmmdc = euclid(x1, x2, alpha1, beta2);

  alpha0 = beta2 % N;
  beta1 =  (alpha1 - beta2 * c1) % N;
  return cmmdc;
}

int main () {
  cin >> A >> N;
  int64_t x, y, cmmdc;
  cmmdc = euclid(N, A, x, y);  
  cout << (y % N + N ) % N;  
  return 0;
}