#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
ll plmplmplmpl(ll a, ll b, ll &x, ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll t=plmplmplmpl(b, a%b, x, y);
    ll aux=x;
    x=y;
    y=aux-y*(a/b);
    return t;
}
int main(){
    ll a, n,x,y;
    in>>a>>n;
    plmplmplmpl(a, n, x, y);
    out<<(x+n)%n;
    return 0;
}