#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
typedef long long ll;
int a, mod;
void inv_mod(ll &inv, ll &ins, int a, int b) {
  if(b == 0) {
    inv = 1;
    ins = 0;
  } else {
    inv_mod(inv, ins, b, a % b);
    swap(inv, ins);
    ins -= inv * (a / b);
  }
}
int main()
{
  in >> a >> mod;
  ll inv = 0, ins;
  inv_mod(inv, ins, a, mod);
  if(inv <= 0)
    inv = (inv + mod) % mod;
  out << inv << '\n';
  in.close();
  out.close();
  return 0;
}