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

int main()
{
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f>>n>>mod;
	aux=mod;
	phi=mod;
	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(aux!=1)
	{
		phi=(phi/aux)*(aux-1);
	}
	g<<putere(n, phi-1);
}