#include<fstream.h>
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
long long a,b,q,r,ai,n;
long long s,s1,s2,t,t1,t2;
int main()
{f>>ai>>n; a=ai; b=n;
 s1=1; t1=0; 
 s2=0; t2=1;
 r=a%b; q=a/b;
 while(r)
  {s=s1-s2*q; s1=s2; s2=s;
   t=t1-t2*q; t1=t2; t2=t;
   a=b; b=r; r=a%b; q=a/b;
  }
 // a*s+n*t=1  
 if(s) g<<s<<'\n'; 
  else
    {while(s<0) s+=n;
     g<<s<<'\n';  
	}
 g.close(); return 0;
}