#include <iostream>
#include <fstream>

int MODULO;

void gcd(long long &x, long long &y, int a, int b) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }

  gcd(x, y, b, a % b);
  long long temp = x;
  x = y;
  y = temp - y * (a / b);
}


int main (int argc, char *argv[]) {

  std::ifstream fin("inversmodular.in");
  std::ofstream fout("inversmodular.out");

  long long A, N;
  fin >> A >> MODULO;

  long long t1, t2;
  gcd(t1, t2, A, MODULO);

  if (t1 <= 0) t1 = MODULO + t1 % MODULO;

  fout << t1;
  
  return 0;
}