#include <fstream>
#include <stack>

using namespace std;

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

int x,MOD;

int imod(int x)
{
    stack < pair < int , int > > inStack;
    int y = MOD;

    while (y)
    {
        inStack.push({x,y});
        int aux = x;
        x = y;
        y = aux % x;
    }

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

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

    return inv;
}

int main()
{

f >> x >> MOD;

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

return 0;
}