#include <cstdio>
using namespace std;

int q[1000];

int invm(int a,int n)
{
    //ma bazez pe q global ca sa nu mai pierd timp la alocarea la intrarea in fctzie
    int i=0,x=1,y=0,r,aux,b=n;
    while(b)
    {
        q[++i]=a/b;
        r=a%b;
        a=b;
        b=r;
    }
    while(i)
    {
        aux=y;
        y=x-q[i--]*y;
        x=aux;
    }
    return (n+x)%n;
}

int main()
{
    FILE *f=fopen("inversmodular.in","r");
    int a,n;
    fscanf(f,"%d%d",&a,&n);
    fclose(f);
    f=fopen("inversmodular.out","w");
    fprintf(f,"%d",invm(a,n));
    fclose(f);
    return 0;
}