#include <stdio.h>

void extEuclid(long long A,long long N,long long* x,long long* y) {

    if( N==0 ) {
        (*x)=1;
        (*y)=0;
    }
    else {
        extEuclid(N,A%N,x,y);
        long long aux = (*x);
        (*x) = (*y);
        (*y) = aux - (*y)*(A/N);
    }
}

int main() {

    long long A,N;
    long long inv,ins;

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

    if( f==NULL || g==NULL )
        return 0;
    if ( fscanf(f,"%lld %lld",&A,&N)!=2 )
        return 0; 

    extEuclid(A,N,&inv,&ins);
    if( inv <=0 )
        inv = N + inv%N;
    fprintf(g,"%lld",inv);
}