#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a, b, z=1, x, y, inv, c, r;
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;
}