#include <iostream>
#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

void invModular(long long &inv, long long &ins, int a, int b)
{
    if(!b)
        inv = ins = 1;
    else {
        long long inv1, ins1;
        invModular(inv1, ins1, b, a % b);
        inv = ins1;
        ins = inv1 - ins1 * (a / b);
    }
}

int a, n;

int main()
{
    f>>a>>n;
    long long ins = 0, inv = 0;

    invModular(inv, ins, a, n);

    while(inv < 0)
        inv = inv + n;

    g<<inv;
}