#include <cstdio>

inline void euclid(int a, int b, int *x0, int *y0) {
  int x, y;
  if (!b) {
    x = 1;
    y = 0;
  } else {
    euclid(b, a % b, x0, y0);
    x = *y0;
    y = *x0 - a / b * (*y0);
  }
  *x0 = x;
  *y0 = y;
}

int main() {
  int n, x, y, a;
  FILE *f = fopen("inversmodular.in", "r");
  fscanf(f, "%d%d", &a, &n);
  fclose(f);
  euclid(a, n, &x, &y);
  x = x % n < 0 ? x % n + n : x % n;
  f = fopen("inversmodular.out", "w");
  fprintf(f, "%d\n", x);
  fclose(f);
  return 0;
}