#include <stdio.h>

int N,M;

void euclid(long long &x, long long &y ,int a, int b)
{
    long long aux;
    if (b==0)
        {
            x=1;
            y=0;
        }
        else
        {
            euclid(x,y,b,a%b);
            aux=x;
            x=y;
            y=aux-y*(a/b);
        }
}

int main()
{
    long long nr=0,nrr;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d %d", &N,&M);
    euclid(nr,nrr,N,M);
    if (nr<=0)
         nr=M+nr%M;
    printf("%lld", nr);
    return 0;
}