#include <cstdio>
#include <iostream>

using namespace std;

void euclid(long long a, long long b, long long &X, long long &Y)
{ // invariant: a * x + b * y = gcd(a,b)
  if (b == 0) { 
    X = 1;
    Y = 0;
    return;
  }
  long long X_, Y_;
  euclid(b, a % b, X_, Y_);
  /* 
     b * X_ + (a - [a/b]*b) * Y_ 
   */
  X = Y_;
  Y = X_ - a/b * Y_;
}

int main()
{
  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);

  long long a, MOD, X, Y;
  cin >> a >> MOD;
  euclid(a, MOD, X, Y);
  cout << (X % MOD + MOD) % MOD << "\n";
  return 0;
}