#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long a,b,x=1,y,aux;

void euclid(long m,long n);

int main()
{
    f>>a>>b;
    euclid(a,b);
    while(x<0)
        x+=b;
    g<<x%b<<'\n';
    f.close();
    g.close();
    return 0;
}

void euclid(long m,long n){
    if(!n)
        return;
    else{
        euclid(n,m%n);
        aux=y;
        y=x-(m/n)*y;
        x=aux;}}