#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/i) * (i-1);
		}		
	if( nr != 1) 
		res=(res/nr)*(nr-1);
	return res;
	
}
LL lgput( LL N , int P )
{
	LL Sol=1LL;
	while( P )
	{
		if( P&1  )	
			Sol=(Sol*N)%MOD;
		N=(N*N)%MOD;
		P>>=1;
	}
	return Sol;
}


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