#include<stdio.h>
long long inv,ins,aux;
int a,n;
void gcd(long long &x,long long &y,int a,int b){
	if(b==0){
		x=1;
		y=0;
	}else{
		gcd(x,y,b,a%b);
		aux=x;
		x=y;
		y=aux-y*(a/b);
	}
}
int main(){
	FILE *f;
	f=fopen("inversmodular.in","r");
	fscanf(f,"%d%d",&a,&n);
	fclose(f);
	gcd(inv,ins,a,n);
	if(inv<0)
		inv=(n+inv)%n;
	f=fopen("inversmodular.out","w");
	fprintf(f,"%lld",inv);
	fclose(f);
	return 0;
}