#include <cstdio>

using namespace std;
void ee(int a,int b,int &x,int &y,int &d)
{
    if(b==0)
    {
        x=1;
        y=0;
        d=a;
        return ;
    }
    int q=a/b,x1,y1;
    ee(b,a-q*b,x1,y1,d);
    x=y1;
    y=x1-q*y1;
}
int main()
{
    FILE *in,*out;
    in=fopen("inversmodular.in","r");
    out=fopen("inversmodular.out","w");
    int n,i,j,a,b,x,y,d=1,r;
    fscanf(in,"%d%d",&a,&n);
    ee(a,n,x,y,d);
    r=(n+(long long)x%n)%n;
    if(r<0)
        r=r+n;
    fprintf(out,"%d",r);
    return 0;
}