#include<stdio.h>
void euclid(int a,int b,int* x,int* y);
FILE*fin,*fout;
int main()
{
    fin=fopen("inversmodular.in","r");
    fout=fopen("inversmodular.out","w");
    int A,N;
    fscanf(fin,"%d%d",&A,&N);
    int X,Y;
    euclid(A,N,&X,&Y);
    while(X<0)
    {
        X+=N;
    }
    fprintf(fout,"%d",X);
    fclose(fin);
    fclose(fout);
    return 0;
}
void euclid(int a,int b,int* x,int* y)
{
    if(b==0)
    {
        *x=1;
        *y=0;
    }
    else
    {
        int x0,y0;
        euclid(b,a%b,&x0,&y0);
        *x=y0;
        *y=x0-(a/b)*y0;
    }
}