#include <fstream>
using namespace std;

int A,N;
long long Inv;

void cmmdc(long long &X,long long &Y,int A,int B) {

    if(B) {

        cmmdc(X,Y,B,A%B);

        int tmpX=X;
        X=Y;
        Y=tmpX-Y*(A/B);

        }
    else
        X=1,
        Y=0;

}
void solve() {

    long long Y;

    cmmdc(Inv,Y,A,N);

    Inv%=N;
    if(Inv<0)
        Inv+=N;

}
void read() {

    ifstream in("inversmodular.in");
    in>>A>>N;
    in.close();

}
void write() {

    ofstream out("inversmodular.out");
    out<<Inv<<'\n';
    out.close();

}
int main() {

    read();
    solve();
    write();

    return 0;

}