#include <fstream>
#include <iostream>

using namespace std;

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

void modul(long long int a, long long int b, long long int &x, long long int &y){
    if(b == 0){
        x=1;
        y=0;
        return;
    }
    long long int x_, y_;
    long long int q = a/b;
    modul(b, a%b, x_, y_);
    x = y_;
    y = x_ - (a/b) * y_;
}

int main()
{
    long long int a, b, x, y;
    f>>a>>b;
    modul(a, b, x, y);
    g<<(x%b + b)%b;

    return 0;
}