#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,n;
pair<int,int> ee(int a,int b){
    if(b==0)
    return {1,0};
    pair<int,int> r =ee(b,a%b);
    return {r.second,r.first-(a/b)*r.second};

}
int im(int x, int mod){
    int r =ee(x,mod).first;
    if(r<0){
        r=mod+(r%mod);
    }
    return r;
}
int main()
{
    fin>>a>>n;
    fout<<im(a,n);
    return 0;
}