#include <fstream>
#include <bitset>

using namespace std;

const char InFile[]="inversmodular.in";
const char OutFile[]="inversmodular.out";
const int MaxN=44722;

ifstream fin(InFile);
ofstream fout(OutFile);

int A,N,nrp[MaxN<<1];
bitset<MaxN> pciur;

inline void ciur()
{
	for(register int i=2;i<MaxN;++i)
	{
		if(pciur[i]==0)
		{
			nrp[++nrp[0]]=i;
			for(register int j=i<<1;j<MaxN;j+=i)
			{
				pciur[j]=1;
			}
		}
	}
}

inline int mypow(int A, int B)
{
	int sol=1;
	A%=N;
	for(;B;B>>=1)
	{
		if((B&1)==1)
		{
			sol=(1LL*sol*A)%N;
		}
		A=(1LL*A*A)%N;
	}
	return sol;
}

inline int mypow2(int A, int B)
{
	int sol=1;
	for(;B;B>>=1)
	{
		if((B&1)==1)
		{
			sol=sol*A;
		}
		A=A*A;
	}
	return sol;
}

inline int fi(int A)
{
	int sol=1;
	for(register int i=1;i<=nrp[0] && nrp[i]*nrp[i]<=A;++i)
	{
		if(A%nrp[i])
		{
			continue;
		}
		int p=0;
		while(A%nrp[i]==0)
		{
			++p;
			A/=nrp[i];
		}
		sol*=(nrp[i]-1)*mypow2(nrp[i],p-1);
	}
	if(A>1)
	{
		sol*=(A-1);
	}
	return sol;
}

int main()
{
	ciur();
	
	fin>>A>>N;
	fin.close();
	
	fout<<mypow(A,fi(N)-1);
	fout.close();
	return 0;
}