#include<stdio.h>
#define tip long long
tip a,n,m,p,e,k;
void read(),solve(),euler(tip p);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&a,&n);
}
void solve()
{
	e=1;m=n;euler(2);euler(3);
	for(k=1;;k++)
	{
		p=6*k-1;if(p*p>m)break;euler(p);
		p=6*k+1;if(p*p>m)break;euler(p);
	}
	if(m>1)e*=m-1;
	e--;p=1;
	while(e){if(e%2)p=(p*a)%n;a=(a*a)%m;e/=2;}
	printf("%lld\n",p);
}
void euler(tip p)
{
	if(m%p)return;
	e*=p-1;m/=p;while(m%p==0){e*=p;m/=p;}	
}