#include<cstdio>
#include<cmath>
using namespace std;
void read(),solve();
int A,N,M,i,F[10010],k,MOD,SOL,E,D;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("invmod.in","r",stdin);
	freopen("invmod.out","w",stdout);
	scanf("%lld%lld",&A,&N);
}
void solve()
{
	M=N;
	MOD=N;
	D=1;
	for(i=2;i<=sqrt(double(M));i++)
	{
		if(M==1)break;
		if(!(M%i))
		{
			F[++k]=i;
			D*=i;
		}
		else continue;
		while(!(M%i))
			M/=i;
	}
	if(M>1)F[++k]=M;
	E=N/D;
	for(i=1;i<=k;i++)E*=(F[i]-1);
	SOL=1;
	E--;
	for(;E;E/=2)
	{
		if(E%2)
		{
			SOL*=A;
			SOL%=MOD;
		}
		A*=A;
		A%=MOD;
	}
	printf("%lld\n",SOL);
}