#include<fstream.h>
long a,n,x,y,z;
void e2(long a,long b,long *x,long *y)
{long x0,y0;  
if(b==0)
      (*x)=1,(*y)=0;
else
      {e2(b,a%b,&x0,&y0);
      (*x)=y0,(*y)=x0-(a/b)*y0;}}
int main()
{ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
f>>a>>n;
e2(a,n,&x,&y);
z=x;
while(z<1)
      z+=n;
while(z>n)
      z-=n;
g<<z;
f.close();
g.close();
return 0;}