#include<fstream>
using namespace std;

int n,m,p;
long long x;

int phi(int m)
{
	int i,x=m;
	for (i=2;i*i<=m;i++)
		if (m%i==0)
		{
			while (m%i==0)
				m/=i;
			x=x/i*(i-1);
		}
	if (m!=1)
		x=x/m*(m-1);
	return x;
}		

void pw(int p)
{
	if (p==1)
		x=n;
	else if (p%2==0)
	{
		pw(p/2);
		x=x*x%m;
	}
	else
	{
		pw(p-1);
		x=x*n%m;
	}
}

int main()
{
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f >> n >> m;
	p=phi(m)-1;
	pw(p);
	g << x;
}