#include<fstream>
using namespace std;
ifstream F("inversmodular.in");
ofstream G("inversmodular.out");
#define L long long
L a,b,d,x,y;
void A(L a,L b,L *d,L *x,L *y)
{
    if(!b)
        *d=a,*x=1,*y=0;
    else {
        L e,f;
        A(b,a%b,d,&e,&f),*x=f,*y=e-(a/b)*f;
    }
}
int main()
{
    return F>>a>>b,A(a,b,&d,&x,&y),G<<(y<0?b-y%b:y%b),0;
}