#include <fstream>

#define nMax 100001

using namespace std;

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

int euclid(int a, int b, int &x, int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }

    int x1, y1, d;
    d=euclid(b, a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;

    return d;
}

int main()
{
    int x, y, d, a, MOD;
    fin>>a>>MOD;
    d=euclid(a, MOD, x, y);
    while(x<0)
        x+=MOD;
    fout<<x;
}