#include <bits/stdc++.h>
using namespace std;

using ll = long long;

tuple<ll, ll> euclid_extins(const ll a, const ll b){
    ll x_, y_;
    return (b == 0 ? make_tuple(1ll, 0ll) :
        (tie(y_, x_) = euclid_extins(b, a%b),
        make_tuple(x_, y_ - (a/b)*x_))); }

ll inv_mod(const ll x, const ll p){
    const auto tmp = euclid_extins(x, p);
    return ((get<0>(euclid_extins(x, p))%p)+p)%p; }

int main(){
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    ll x, y;
    f >> x >> y;

    g << inv_mod(x, y);
    return 0;
}