#include <iostream>
#include <fstream>
using namespace std;
int x[35],y[35],A,N;
void gcde(int A,int B,int lev)
{
    if(B==0)
    {
        x[lev]=1;
        return;
    }
    gcde(B,A%B,lev+1);
    x[lev]=y[lev+1];
    y[lev]=x[lev+1]-(A/B)*y[lev+1];
}
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>A>>N;
    gcde(A,N,1);
    if(x[1]<0)
    {
        x[1]%=N;
        x[1]+=N;
    }
    g<<x[1];
    return 0;
}