#include<stdio.h>

int main(void)
{
    int a, m, r, c, y; 
    int y0=0 ,y1=1;

    FILE *f, *g;

    f=fopen("inversmodular.in","r");
    g=fopen("inversmodular.out","w");

    fscanf(f,"%d %d", &a, &m);
    int aux=m;

    while(a!=0)
    {
        r=m%a;
        c=m/a;
        m=a;
        a=r;
        y=y0-c*y1;
        y0=y1;
        y1=y;
    }
 while(y0<0)
    {
        y0+=aux;
    }

    fprintf(g,"%d",y0);

    fclose(f);
    fclose(g);
}