#include<stdio.h>

int main(void)
{
    FILE *f1 , *f2;
    f1=fopen("inversmodular.in" , "r");
    f2=fopen("inversmodular.out", "w");
    int a , m , y0=0 , y1=1 , r , c , y;
    fscanf(f1 , "%d %d" , &a , &m);
    int aux=m;
    while(a)
    {
        r=m%a;
        c=m/a;
        m=a;
        a=r;
        y=y0-c*y1;
        y0=y1;
        y1=y;
    }
    while(y0<0)
    {
        y0+=aux;
    }
    fprintf(f2 , "%d" , y0);
    return 0;
}