#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int T;
int GCD(int A, int B, int & X, int & Y)
{
    if(B==0)
    {
        X=1;Y=0;
        return A;
    }
    int D,X0,Y0;
    D=GCD(B,A%B,X0,Y0);
    X=Y0;
    Y=X0-(A/B)*Y0;
    return D;
}
int main()
{
    int A,B,D,X,Y;
    fin>>A>>B;
    D=GCD(A,B,X,Y);
    if (X<0) X+=N
    fout<<X<<"\n";
    return 0;
}