#include <stdio.h>
#include <stdlib.h>

int power(int m, int k, int p){
	int ans=1;
	long int n=m;
	n=n%p;
	while(k>0){
		if(k&1)
			ans=(ans*n)%p;
		k=k>>1;
		n=(n*n)%p;
	}
	return ans;
}

int inversMod(int x, int p){
	return power(x,p-2,p);
}

int main(){
	int a,n;
	FILE *f,*g;
	if((f=fopen("inversmodular.in","r"))==NULL){
		printf("eroare deschidere fisier\n");
		exit(1);
	}
	if((g=fopen("inversmodular.out","w"))==NULL){
		printf("eroare deschidere fisier\n");
		exit(1);
	}
	fscanf(f,"%d",&a);
	fscanf(f,"%d",&n);
	fprintf(g,"%d",inversMod(a,n));
	fclose(f);
	fclose(g);
	return 0;
}