#include <iostream>
#include <fstream>
using namespace std;

typedef long long ll;

struct trip{
    ll a, b, c;
    trip(const ll e, const ll f, const ll g):
        a(e), b(f), c(g){}
};

trip euclid_extins(const ll a, const ll b){
    if(b == 0){
        return trip(1, 0, a);
    }
    const trip t = euclid_extins(b, a%b);
    return trip(t.b, t.a - (a/b) * t.b, t.c);
}

ll inv_mod(const ll a, const ll n){
    const trip t = euclid_extins(a, n);
    return (t.a%n + n)%n;
}

int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    ll a, n;
    f >> a >> n;
    g << inv_mod(a, n) << endl;
    return 0;
}