#include <iostream>
#include <fstream>
#include <vector>

#define fi first
#define se second
#define pb push_back
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
typedef long long ll;
typedef pair <ll, ll> pll;

vector<pll> v;
ll t;

ll extgcd(ll a, ll b, ll &ca1, ll &cb1){ // calculate gcd as well as x, y from {Z} such as a*x+b*y=gcd
    ca1=1, cb1=0;
    ll ca2=0, cb2=1, r, d;
    while (b!=0){
        r=a%b; d=a/b;
        a=b; b=r;
        ca1-=d*ca2; cb1-=d*cb2;
        swap(ca1, ca2); swap(cb1, cb2);
    }
    return a;
}
ll inv(ll x, ll m){
    ll ca, cb;
    extgcd(x, m, ca, cb);
    if (ca<=0)
        ca=ca%m+m;
    return ca;
}
inline pll CRT(vector <pll> &v){
    ll M=1;
    for (auto it:v)
        M*=it.se;

    pll sol{0, M};
    for (auto it:v)
        sol.fi=(sol.fi+it.fi*(M/it.se)%M*inv(M/it.se, it.se))%M;
    return sol;
}

int main(){
    /*cin>>t;
    while (t--){
        v.clear();
        ll a, b;
        cin>>a>>b;
        v.pb({a, b});
        cin>>a>>b;
        v.pb({a, b});

        auto sol=CRT(v);
        cout<<sol.fi<<' '<<sol.se<<'\n';
    }*/
    ll A, N;
    fin>>A>>N;
    fout<<inv(A, N);
    return 0;
}