#include <fstream>
#define SL long long
using namespace std;
void cmmdc(SL &x,SL &y, SL a, SL b)
{
  if (b==0)
    {
        x=1;
        y=0;
        return;
    }
  SL x0,y0;
    cmmdc(x0,y0,b,a%b);
    x=y0;
    y=x0-(a/b)*y0;
}
ifstream in;
ofstream out;
SL N,i,j,k,M,X,Y;
int main() {
    in.open("inversmodular.in");
    out.open("inversmodular.out");
    in >> N >> M;
    cmmdc(X, Y,N,M);
    while (X<=0)
      X=M+X%M;
    out << X;
    out.close();
    return 0;
}