#include<cstdio>
using namespace std;
long long a,n,m,k,i,p[30],sol;
int main()
{
	freopen("invmod.in","r",stdin);
	freopen("invmod.out","w",stdout);
	scanf("%lld%lld", &a, &n);
	m=n;
	for(i=2;i*i<=m;i++)
	{
		if(m==1)break;
		if(m%i)continue;
		p[++k]=i;
		while(m%i==0)m/=i;
	}
	if(m!=1)p[++k]=m;
	m=n;
	for(i=1;i<=k;i++)n/=p[i];
	for(i=1;i<=k;i++)n*=p[i]-1;
	sol=1;n--;
	while(n)
	{
		if(n%2)sol=(sol*a)%m;
		a=(a*a)%m;
		n/=2;
	}
	printf("%lld", sol);
	return 0;
}