#include<fstream>
#include<algorithm>

#define LL long long

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int A,MOD;

LL get_phi ( LL nr )
{  
	LL res=nr;
	for( LL i(2) ; i*i <= nr ; ++i )
		if( nr % i ==0 )
		{
			while( nr %i == 0 )
				nr/=i;
			res = res-(res/i);
		}
	if( nr > 1) 
		res=res-res/(nr);
	return res;
	
}
LL lgput( int N , int P )
{
	int Sol=1;
	while( P )
	{
		if( P&1 )
			Sol=(Sol*N)%MOD;
		N=(N*N)%MOD;
		P>>=1;
	}
	return Sol;
}


LL inverse ( int N , int P )
{
	return lgput(N,P-1);
}
int main ( void )
{
	f>>A>>MOD;
	g<<inverse(A,get_phi(MOD));
	f.close();
	g.close();
	return 0;
}