#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a, b, x, y, z=1, inv, r, c;
int main()
{
    f >> a>> b;
    inv = b;
    while( a )
    {
        r = b%a;
        c = b/a;
        b = a;
        a = r;
        x =y-c*z;
        y = z;
        z = x;
    }
    while( y < 0 )
         y += inv;

    g << y<<"\n" ;
    return 0;
}