#include <iostream>
#include <fstream>
#define ll long long

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");

pair<ll, ll>invers(ll x, ll y)
{
    if(y == 0) return {1, 0};
    auto p = invers(y, x%y);
    return {p.second, p.first - p.second*(x/y)};
}

int main()
{
    int a, n;
    fin >> a >> n;
    ll b = invers(a, n).first;
    while(b < 0) b+=n;
    fout << b;
    return 0;
}