#include <iostream>
#include <fstream>

using namespace std;

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

int modulo;

int cmmdc(int a, int b, int &x, int &y){
  if(b == 0){
    x = 1;
    y = 0;
    return a;
  }else{
    int ans = cmmdc(b, a % b, x, y);
    int xPrim = x, yPrim = y;
    x = yPrim % modulo;
    y = (xPrim - (a / b) * yPrim) % modulo;
    return ans;
  }
}

int main()
{
  int n, m, x, y, ans;
  in >> n >> m;
  modulo = m;
  ans = cmmdc(n, m, x, y);
  out << x;
  return 0;
}