#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int64_t cmmdc(int64_t a,int64_t b,int64_t &x,int64_t &y)
{
    if(b==0){x=1;y=0;return a;}
    int64_t X,Y,D;
    D=cmmdc(b,a%b,X,Y);
    x=Y;y=X-(a/b)*Y;
    return D;
}
int main()
{
    int64_t A,N,x,y,d;
    f>>A>>N;
    d=cmmdc(A,N,x,y);
    x%=N;
    if(x<0)x+=N;
    g<<x;
    return 0;
}