#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int mod(int a)
{
	if(a>=0) return a%3;
	else return (3+a)%3;
}

int main()
{
	int x[3]={1,0},y[3]={0,1},r[3],i=0,a,n,q;
	
	i=1;
	f>>a>>n; 

	r[0]=a; r[1]=n; 
	x[0]=1; y[0]=0; 
	x[1]=0; y[1]=1;
	while(r[mod(i-1)]%r[i] != 0)
	{
		i=(i+1)%3;
		r[i]=r[mod(i-2)]%r[mod(i-1)];
			
		q=r[mod(i-2)]/r[mod(i-1)];
		x[i]=x[mod(i-2)]-x[mod(i-1)]*q;
		y[i]=y[mod(i-2)]-y[mod(i-1)]*q;
	}
	
	if(x[i]<0) while(x[i]<0) x[i]+=n;	
	g<<x[i];
}