#include <iostream>
#include <fstream>

using namespace std;

pair < long, long > EExtins(long long x, long long y)
{
    if(y==0)
    {
        return {1,0};
    }

    auto p = EExtins(y,x%y);
    long long d = x/y;
    return {p.second, p.first - d * p.second};
}

long long A,N;

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

    fin >> A >> N;
    auto p = EExtins(A,N);
    while(p.first < 0)
        p.first += N;

    fout << p.first;

    return 0;
}