#include <stdio.h>

void invers_modular(long long a, long long b, long long *x, long long *y)
{
  if(b == 0){
    *x = 1;
    *y = 0;
    return;
  }
  long long X, Y;
  invers_modular(b, a % b, &X, &Y);
  *x = Y;
  *y = X - (a / b) * Y;
}

int main(void)
{
  FILE *fin = fopen("inversmodular.in", "r");
  FILE *fout = fopen("inversmodular.out", "w");
  long long a, n, x, y;
  fscanf(fin, "%lld %lld", &a, &n);
  invers_modular(a, n, &x, &y);
  long long result = (x % n + n) % n;
  fprintf(fout, "%lld\n", result);
  fclose(fin);
  fclose(fout);
  return 0;
}