#include<stdio.h>
int a[200],b[200],inv[200],aux[200],n;
int readd()
{
	FILE *f=fopen("inversmodular.in","r");
	
	fscanf(f,"%d%d",&a[1],&b[1]);
	int c=1;
    int 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()
{      
    int inv= readd();
    FILE *f= fopen("inversmodular.out","w");
    fprintf(f,"%d",inv);
	return 0;
}