#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int A,N;

int inv(int a,int M)
{
    int y0=0,y1=1,y;
    int tmp=M;
    int rest,cat;

    while(a!=0)
    {
        rest=tmp%a;
        cat=tmp/a;

        tmp=a;
        a=rest;

        y=y0-cat*y1;
        y0=y1;
        y1=y;
    }

    while(y0<0) y0+=M;

    return y0;
}

int main()
{
    f>>A>>N;
    g<<inv(A,N);
}