#include <fstream>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
long long n,k;
pair<long long,long long> inv(long long a,long long b)
{
    if (b==0)
    return make_pair(1,0);
    long long xx=0,yy=0,x=0,y=0;
    pair<long long,long long> l=inv(b,a%b);
    xx=l.first;
    yy=l.second;
    x=yy;
    y=xx-yy*(a/b);
    return make_pair(x,y);
}
int main()
{
    in>>n>>k;
    out<<((inv(n,k).first)%k+k)%k;
    return 0;
}