#include <fstream>

using namespace std;

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

void inv_mod (int a, int p, long long int &x, long long int &y)
{
    if (p==0) {x=1; y=0;}
    else
    {
        long long int x0, y0;
        inv_mod(p, a%p, x0, y0);
        x=y0;
        y=x0-(a/p)*y0;
    }
}

int main(){
    long long x=0,y=0;
    int a,p;

    f>>a>>p;

    inv_mod(a,p,x,y);

    if(x<=0)
        x=y+x%y;

    g<<x;


return 0;
}