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