#include <fstream>

using namespace std;

class obj{
public:
  long long x, y, ans;

  obj(){};

  obj(int a, int b, int c){
    x = a;
    y = b;
    ans = c;
  }

  obj operator * (long long other){
    obj we(x * other, y * other, ans * other);
    return we;
  }

  obj operator -(obj other){
    obj we(x - other.x, y - other.y, ans - other.ans);
    return we;
  }
};

obj gcd(obj x, obj y){
  obj z;
  while(y.ans){
    z = x;
    x = y;
    y = z - y * (z.ans / y.ans);
  }
  return x;
}

int main(){
  ifstream in("inversmodular.in");
  ofstream out("inversmodular.out");

  int a, b;
  in >> a >> b;
  obj one(1, 0, a), two(0, 1, b);
  obj three = gcd(one, two);
  out << ((three.x % b) + b) % b;

  return 0;
}