using namespace std;

#include <cstdio>
#define ll long long

ll rez,a,N,A;
ll pow(ll x,ll p)
{
	return (!p?1:(p&1?x * pow(x,p-1):(a = pow(x,p>>1))*a) ) % N;
}

ll phi(ll x,ll i)
{
	return !(x%i)?phi(x/i,i+( ((x/i)%i)?(a=a/i*(i-1))-a:0)):(x/(++i)>=i?phi(x,i):(x^1?a/x*(x-1):a));
}

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