#include <fstream>
#define int long long
using namespace std;

signed main(){

  ifstream fin ("inversmodular.in");
  ofstream fout ("inversmodular.out");

  int y0, y1, m, a, r, c, y;
  fin >> a >> m;

  int aux;
  aux = m;

  y0 = 0;
  y1 = 1;
  while (a != 0){
    c = m / a;
    r = m % a;
    m = a;
    a = r;
    y = y0 - c * y1;
    y0 = y1;
    y1 = y;
  }

  while (y0 < 0) y0 += aux;

  fout << y0;
  return 0;
}