#include<fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
typedef long long ll;
void cmmdc(ll &x,ll &y,ll a,ll b){
    if(b==0){
        x=1; y=0;
        return;
    }
    ll x0,y0;
    cmmdc(x0,y0,b,a%b);
    x=y0;
    y=x0-y0*(a/b);
}
int main(){
    ll a,n,x,y;
    cin>>a>>n;
    cmmdc(x,y,a,n);
    if(x<0) x+=n;
    cout<<x;
}