#include <iostream>
#include <fstream>

using namespace std;

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

typedef long long ll;

int a, n;
ll inv, ins;

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 >> n;

  inv_mod(inv, ins, a, n);

  inv = (inv + n) % n;

  out << inv << '\n';

  in.close();
  out.close();

  return 0;
}