#include<fstream>
using namespace std;
ifstream F("inversmodular.in");
ofstream G("inversmodular.out");
int a,b,d,x,y;
void A(int a,int b,int *d,int *x,int *y)
{
    if(!b)
        *d=a,*x=1,*y=0;
    else {
        int 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<<(x<0?b-x%b:x),0;
}