#include<stdio.h>
long long a[200],b[200],inv[200],aux[200],n;
long long invers_modular()
{
	
	long long c=1;
    long long i=1;
	while(b[i])
    {
        a[i+1]=b[i];
        b[i+1]=a[i]%b[i];i++;
    }
	n=i;
    aux[n]=0;
	inv[n]=c/a[n];
    for(i=n-1;i>=1;i--)
	{ 
        inv[i]=aux[i+1];
        aux[i]=inv[i+1]-(a[i]/b[i])*aux[i+1];
    }
	while(inv[1]>=b[1])
        inv[1]=inv[1]-b[1];
    while(inv[1]<0)
        inv[1]=inv[1]+b[1];
    return inv[1];
}
int main(void)
{   
    FILE *f=fopen("inversmodular.in","r");
	fscanf(f,"%lld%lld",&a[1],&b[1]);   
    long long inv= invers_modular();
   f= fopen("inversmodular.out","w");
    fprintf(f,"%lld",inv);
	return 0;
}