#include <fstream>
#include <stack>

using namespace std;

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

int x , mod;

int imod(int x , int mod)
{
    stack < pair < int , int > > is;
    int y = mod , aux , inv , ins;

    while (y)
    {
        is.push(make_pair(x , y));
        aux = x;
        x = y;
        y = aux % x;
    }

    inv = 1 , ins = 0;
    while (is.size())
    {
        x = is.top().first;
        y = is.top().second;
        is.pop();

        aux = inv;
        inv = ins;
        ins = aux - (x / y) * ins;
    }

    if (inv < 0) inv += mod;

    return inv;
}

int main()
{

f >> x >> mod;

g << imod(x , mod) << '\n';

return 0;
}