#include <fstream>
using namespace std;
int mod, n, aux, phi, i;
int putere(int a, int b)
{
	if(b==0)
		return 1;
	if(b%2)
		return (a*putere(a, b/2)*putere(a, b/2))%mod;
	else return (putere(a, b/2)*putere(a, b/2))%mod;
}

int main()
{
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f>>n>>mod;
	aux=n;
	phi=n;
	for(i=2; i*i<=aux; i++)
	{
		if(aux%i==0)
		{
			phi=(phi*i)/(i-1);
			aux/=i;
		}
		while(aux%i==0)
			aux/=i;
		if(i!=2)
			i++;
	}
	if(aux!=1)
	{
		phi=(phi*aux)/(aux-1);
	}
	g<<putere(n, phi-1);
}