#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll x , MOD , inv , ins;

void gcd(ll &x , ll &y , ll a, ll b)
{
    if (!b)
        x = 1, y = 0;
    else
    {
        gcd(x , y , b , a % b);
        ll aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%lld %lld", &x, &MOD);

    gcd(inv , ins , x , MOD);
    if (inv < 0) inv = inv % MOD + MOD;

    printf("%lld\n", inv);

    return 0;
}