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