#include <fstream>
#include <iostream>
using namespace std;
template <class T>
pair<T, T> gcd_ext(T a, T b, T c) {
 if (b == 0) {
  if (c % a == 0)
   return make_pair(c/a, 0);
  else
   return make_pair(0, 0);
 }
 auto p = gcd_ext(b, a % b, c);
 return make_pair(p.second, p.first - (a/b) * p.second);
}
int main(int argc, char const *argv[])
{
 ifstream fin("inversmodular.in");
 ofstream fout("inversmodular.out");
 long int A, N; fin >> A >> N;
 auto p = gcd_ext<long int>(A, N, 1);
 long int x = p.first;
 x %= N;
 if (x < 0) x += N;
 fout << x << endl;
 return 0;
}