#include <fstream>
using namespace std;
long long mod, n, aux, phi, i;
long long putere(long long x, long long n)
{
	int p = 1 ;
	while (n)
	{
		if (n %2==1) // n este impar
		{
			p *= x; p%=mod;
			n-- ;
		}
		x = x * x ; x%=mod;
		n/=2;
	}
	return p ;
}
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);
}