#include <stdio.h>


void inv(long long *S1,long long *S2,long long A, long long N)
{
    if(N!=0)
    {
        inv(S1,S2,N,A%N);
        long long AA=*S1;
        *S1=*S2;
        *S2=AA-*S2*(A/N);
    }
    else
    {
        *S1=1;
        *S2=0;
    }
    

}
int main()
{
    FILE *in =fopen("inversmodular.in","r");
    FILE *out = fopen("inversmodular.out","w");

    long long A,N;

    fscanf(in,"%lld %lld",&A,&N);
    long long S1=0,S2=0;
    inv(&S1,&S2,A,N);
    if (S1 <= 0)
       S1=S1%N+N;
    fprintf(out,"%lld",S1);


}