#include <stdio.h>

FILE* fin, * fout;

int a, n;

int invers(int a, int n) {
 int t = n;
 int v[2], v1[2] = { 1,0 }, v2[2] = { 0,1 };
 while (n) {
  int q, r;
  q = a / n;
  r = a % n;
  v[0] = v1[0], v[1] = v1[1];
  v1[0] = v2[0], v1[1] = v2[1];
  v2[0] = v[0] - q * v2[0], v2[1] = v[1] = q * v2[1];

  a = n;
  n = r;
 }

 int alfa = v1[0] % t;
 if (alfa < 0) alfa += t;

 return alfa;
}

int main() {
 fin = fopen("inversmodular.in", "r");
 fout = fopen("inversmodular.out", "w");

 fscanf(fin, "%i %i", &a, &n);

 fprintf(fout, "%i", invers(a, n));

 return 0;
}