#include<fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int A,N,x,y;
int cmmdc(int a,int b)
{
	if(b==0)
		return a;
	else 
		return cmmdc(b,a%b);
}
void cmmdc1(int a,int b, int &x,int &y)
{
	if(b==0)
	{
		x=1;y=0;
	}
	else {
		int x0;int y0;
		cmmdc1(b,a%b,x0,y0);
		x=y0;
		y=x0-(a/b)*y0;
	}
}
int main()
{
	f>>A>>N;
	cmmdc1(A,N,x,y);
	while(x<0)
		x+=N;
	g<<x%N;
	return 0;
}