#include <stdio.h>

#define ll long long

void euclid(int A, int B, ll int *X, ll int *Y) {
  if (!B) {
    *X = 1, *Y = 0;
  } else {
    ll int X0, Y0;
    euclid(B, A % B, &X0, &Y0);

    *X = Y0;
    *Y = X0 - 1LL * Y0 * (A / B);
  }
}

int main(void) {
  int A, N;
  ll int X, Y;
  FILE *f = fopen("inversmodular.in", "r");

  fscanf(f, "%d %d", &A, &N);
  fclose(f);

  f = fopen("inversmodular.out", "w");

  euclid(A, N, &X, &Y);
  fprintf(f, "%lld\n", (ll)((X % N + N) % N));
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}