#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long a,b,in,x,y,r,z=1,c;
int main()
{
    f>>a>>b;
    in=b;
    while(a)
    {
        r=b%a;
        c=b/a;
        b=a;
        a=r;
        x=y-c*z;
        y=z;
        z=x;
    }
        while(y<0)
            y=y+in;
        g<<y;


    return 0;
}