#include <fstream>
using namespace std;

long long int N, A, X, Y;
void citire();
void euclid (long long int a, long long int b, long long int &x, long long int &y);
void afisare();

int main()
{
    citire();
    euclid (A, N, X, Y);
    if (X<0) X=N+X%N;
    afisare();
    return 0;
}

void citire()
{
    ifstream fin ("inversmodular.in");
    fin>>A>>N;
    fin.close();
    return;
}

void afisare()
{
    ofstream fout ("inversmodular.out");
    fout<<X<<"\n";
    fout.close();
    return;
}

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

    long long int x0, y0;
    euclid (b, a%b, x0, y0);

    x=y0;
    y=x0-a/b*y0;
}