#include<fstream.h>

long eu(long a, long b, long &x, long &y)
{
 if(b==0)
  {
   x=1;
   y=0;
   return a;
   }
 long d,x0,y0;

 d=eu(b,a%b,x0,y0);
 x=y0;
 y=x0-(a/b)*y0;
 return d;
 }

int main()
{

 long n,a,x,y;
 ifstream f("inversmodular.in");
 ofstream g("inversmodular.out");
 f>>a>>n;
 eu(n,a,x,y);
 while(y<0)y+=n;
 while(y>n)y-=n;
 g<<y;
 return 0;
 }