#include <fstream>

using namespace std;

pair<int, int> Euclid(int a, int b)
{
  if (b == 0) {
    return {1, 0};
  }

  auto p = Euclid(b, a % b);
  return {p.second, p.first - (a / b) * p.second};
}

int ModInv(int num, int mod)
{
  auto p = Euclid(num, mod);
  while (p.first < 0) {
    p.first += mod;
  }
  return p.first;
}

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

  int a, mod;
  fin >> a >> mod;

  auto res = ModInv(a, mod);
  fout << res << "\n";

  return 0;
}