#include<stdio.h>
#define ll long long 

ll a,n;

ll PHI(ll x)
{
	int i=0;
	ll p=x;
	for(i=2;i*i<=x;++i)
	{
		if(!(x%i)) 
		{
			while(!(x%i)) x/=i;
			p/=i;
			p*=(i-1);
		}
	}
	if(x>1) 
	{
		p/=x;
		p*=(x-1);
	}
	
return p;
}

ll put(ll x)
{
	return x*x;
}

ll rid(ll a,ll b,ll n)
{
	if(b==1) return a%n;
	if(b%2==1) 
		return (put(rid(a,(b-1)/2,n))*a%n)%n;
	else 
		return (put(rid(a,b/2,n)))%n;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	
	scanf("%lld%lld",&a,&n);
	
	ll phi=PHI(n)-1;
	ll rez=rid(a,phi,n);
	
	printf("%lld\n",rez);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}