#include <iostream>
#include <fstream>
using namespace std;
 ifstream f("inversmodular.in");
 ofstream g("inversmodular.out");

 int num,n,v[32];

 int Euclid(int a,int b)
 { int i,c,d,x,y,x0,y0,p=0;

     while(b)
     { p++; v[p]=a/b;
        c=a%b;
       a=b; b=c;
     }
     d=a;
    x0=1; y0=0;

    for(i=p;i>=1;i--)
    { x=y0; y=x0-v[i]*y0;
      x0=x; y0=y;
    }

    while(x<0) x+=n;

    return x;
 }
int main()
{ f>>num>>n;

    g<<Euclid(num,n)<<"\n";

    return 0;
}