#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int main()
{
    int a,n;
    fin >> a >> n;
    int y,nr,r,r2,rest,aux;
    long long x;
    x=1,y=0;
    r=a,r2=n;
    while(r2!=0)
    {
        rest=r%r2;
        aux=r/r2;
        nr=x-aux*y;
        x=y;
        y=nr;
        r=r2;
        r2=rest;
    }
    x+=n;
    x%=n; /// ptr x<0
    fout << x;
    return 0;
}