#include <iostream>
#include <fstream>
#include <algorithm>

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;
}
int64_t inversModular(int64_t a,int64_t mod)
{
    if(__gcd(a,mod)>1)
    {
        cerr<<"A nu este inversabil";
        return 0;
    }
    int64_t x,y;
    cmmdc(a,mod,x,y);
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
int main()
{
    int64_t A,N;
    f>>A>>N;
    g<<inversModular(A,N);
    return 0;
}