#include <fstream>

using namespace std;
typedef long long ll;

void extgcd(ll n, ll a, ll &y, ll &x)
{
    if (a == 0) { y = 1; x = 0; return; }
    extgcd(a, n%a, y, x);
    ll x0 = x, y0 = y;
    y = x0;
    x = y0 - (n / a) * x0;
    return;
}

int main()
{
    ifstream f ("inversmodular.in");
    ofstream g ("inversmodular.out");
    ll A, N, Y, X;
    f >> A >> N;
    extgcd(N, A, Y, X);
    while (X < 0) X += N;
    g << X % N << '\n';

    return 0;
}