#include<fstream>
using namespace std;
void cmmdc(int a, int b, long long &x, long long &y){
  if(b){
    cmmdc(b,a%b,x,y);
    long long aux=y;
    y=x-(a/b)*y;
    x=aux;
  }
  else
  {
        x=1;
        y=0;
  }
}
int main()
{
        int n, a;
        long long x, y;
        ifstream f("inversmodular.in");
        f>>a>>n;
        f.close();
        cmmdc(a,n,x,y);
        while(x<0)  x+=n;
        ofstream g("inversmodular.out");
        g<<x<<'\n';
        g.close();
        return 0;
}