#include <bits/stdc++.h>
using namespace std;
void invMod(int a, int b, int &x, int &y) {
 if (!b)
  x = 1, y = 0;
 else {
  int x0, y0;
  invMod(b, a % b, x0, y0);
  x = y0;
  y = x0 - (a / b) * y0;
 }
}
int main() {
 ifstream cin ("inversmodular.in");
 ofstream cout ("inversmodular.out");
 int a, p;
 cin >> a >> p;
 int x, y;
 invMod(a, p, x, y);
 if (x <= 0)
  x += p;
 cout << x;
 return 0;
}